如何使用 C# 找到接近给定目标的唯一三元组?
csharpserver side programmingprogramming更新于 2025/4/18 10:22:17
双指针模式，类似于三元组和为零。我们可以采用类似的方法遍历数组，一次取一个数字。在每一步中，我们都会保存三元组和目标数字之间的差异，并在每一步中将其与迄今为止的最小目标差异进行比较，以便最终返回总和最接近的三元组。
时间复杂度
对数组进行排序将需要 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
