如何使用C#找到接近目标的四元组？

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

时间复杂度

对数组进行排序将花费 O(N* logN)。总体fourSumClosest()上将采用 O(N * logN + N^3)，它渐近等价于 O(N^3)。

空间复杂度

上述算法的空间复杂度将是O(N)排序所需的。

示例

public class Arrays{
   public int FourSumClosestToTarget(int[] nums, int target){
      if (nums == null ||nums.Length== 0){
         return -1;
      }
      int[] newNums = nums.OrderBy(x => x).ToArray();
      int initialSum = newNums[0] + newNums[1] + newNums[2] + newNums[3];
      for (int i = 0; i < nums.Length; i++){
         for (int j = i; j < nums.Length; j++){
            int left = j + 1;
            int right =nums.Length- 1;
            while (left < right){
               int nearestSum = newNums[i] + newNums[j] + newNums[left] + newNums[right];
               if (nearestSum < initialSum){
                  initialSum = nearestSum;
               }
               if (nearestSum == target){
                  return nearestSum;
               }
               else if (nearestSum < target){
                  left++;
               }
               else{
                  right--;
               }
            }
         }
      }
     return initialSum;
   }
}

static void Main(string[] args){
   Arrays s = new Arrays();
   int[] nums = { 1,0,-1,0,-2,2 };
   var ss = FourSumClosestToTarget(nums,0);
   Console.WriteLine(ss);
}

0