如何使用 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