如何使用 C# 找到接近给定目标的唯一三元组？

Z时代
2024-01-10
分类：综合

两个指针模式，类似于三元组和为零。我们可以按照类似的方法遍历数组，一次取一个数字。在每一步，我们都会保存三元组和目标数之间的差值，并在每一步将它与迄今为止最小的目标差值进行比较，以便最终我们可以返回总和最接近的三元组。

时间复杂度

对数组进行排序将花费 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));
}