数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学如何使用C#查找接近给定目标值的唯一三元组？
双指针模式，类似于三数之和为零。我们可以采用类似的方法迭代数组，每次取一个数字。在每一步，我们将保存三元组与目标数字之间的差值，并在每一步将其与到目前为止的最小目标差值进行比较，以便最终可以返回具有最接近和的三元组。
时间复杂度
对数组进行排序需要O(N*logN)。总的来说，threeSumClosest()需要O(N * logN + N^2)，这在渐近意义上等价于O(N^2)。
空间复杂度
上述算法的空间复杂度为O(N)，这是排序所需的。
示例
public class Arrays{
public int ThreeSumClosest(int[] num, int target){
if (num == null || num.Length == 0){
return -1;
}
int[] nums = num.OrderBy(x => x).ToArray();
int initialclosest = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.Count(); i++){
int left = i + 1;
int right = nums.Length - 1;
while (left < right){
int newClosest = nums[i] + nums[left] + nums[right];
if (Math.Abs(newClosest - target) < Math.Abs(initialclosest - target)){
initialclosest = newClosest;
}
if (newClosest == target){
return newClosest;
}
else if (newClosest < target){
left++;
}
else
{
right--;
}
}
}
return initialclosest;
}
}
static void Main(string[] args){
Arrays s = new Arrays();
int[] nums = { -1, 2, 1, -4 };
Console.WriteLine(s.ThreeSumClosest(nums, 1));
}输出
2
更新于: 2021年8月17日
浏览量 170
广告