3 Sum Closest

Question

  1. Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. 
  2. Return the sum of the three integers. You may assume that each input would have exactly one solution.
  4. For example, given array S = {-1 2 1 -4}, and target = 1.
  5. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

题解1 - 排序 + 2 Sum + 两根指针 + 优化过滤

和 3 Sum 的思路接近，首先对原数组排序，随后将3 Sum 的题拆解为『1 Sum + 2 Sum』的题，对于 Closest 的题使用两根指针而不是哈希表的方法较为方便。对于有序数组来说，在查找 Cloest 的值时其实是有较大的优化空间的。

Python

  1. class Solution:
  2.     """
  3.     @param numbers: Give an array numbers of n integer
  4.     @param target : An integer
  5.     @return : return the sum of the three integers, the sum closest target.
  6.     """
  7.     def threeSumClosest(self, numbers, target):
  8.         result = 2**31 - 1
  9.         length = len(numbers)
  10.         if length < 3:
  11.             return result
  13.         numbers.sort()
  14.         larger_count = 0
  15.         for i, item_i in enumerate(numbers):
  16.             start = i + 1
  17.             end = length - 1
  18.             # optimization 1 - filter the smallest sum greater then target
  19.             if start < end:
  20.                 sum3_smallest = numbers[start] + numbers[start + 1] + item_i
  21.                 if sum3_smallest > target:
  22.                     larger_count += 1
  23.                     if larger_count > 1:
  24.                         return result
  26.             while (start < end):
  27.                 sum3 = numbers[start] + numbers[end] + item_i
  28.                 if abs(sum3 - target) < abs(result - target):
  29.                     result = sum3
  31.                 # optimization 2 - filter the sum3 closest to target
  32.                 sum_flag = 0
  33.                 if sum3 > target:
  34.                     end -= 1
  35.                     if sum_flag == -1:
  36.                         break
  37.                     sum_flag = 1
  38.                 elif sum3 < target:
  39.                     start += 1
  40.                     if sum_flag == 1:
  41.                         break
  42.                     sum_flag = -1
  43.                 else:
  44.                     return result
  46.         return result

源码分析

  1. leetcode 上不让自己导入sys包，保险起见就初始化了result为还算较大的数，作为异常的返回值。
  2. 对数组进行排序。
  3. 依次遍历排序后的数组，取出一个元素item_i后即转化为『2 Sum Cloest』问题。『2 Sum Cloest』的起始元素索引为i + 1，之前的元素不能参与其中。
  4. 优化一——由于已经对原数组排序，故遍历原数组时比较最小的三个元素和target值，若第二次大于target果断就此罢休，后面的值肯定越来越大。
  5. 两根指针求『2 Sum Cloest』，比较sum3和result与target的差值的绝对值，更新result为较小的绝对值。
  6. 再度对『2 Sum Cloest』进行优化，仍然利用有序数组的特点，若处于『一大一小』的临界值时就可以马上退出了，后面的元素与target之差的绝对值只会越来越大。

复杂度分析

对原数组排序，平均时间复杂度为 O(n \log n), 两重for循环，由于有两处优化，故最坏的时间复杂度才是 O(n^2), 使用了result作为临时值保存最接近target的值，两处优化各使用了一个辅助变量，空间复杂度 O(1).

C++

  1. class Solution {
  2. public:
  3.     int threeSumClosest(vector<int> &num, int target) 
  4.     {
  5.         if (num.size() <= 3) return accumulate(num.begin(), num.end(), 0);
  6.         sort (num.begin(), num.end());
  8.         int result = 0, n = num.size(), temp;
  9.         result = num[0] + num[1] + num[2];
  10.         for (int i = 0; i < n - 2; ++i)
  11.         {
  12.             int j = i + 1, k = n - 1;
  13.             while (j < k)
  14.             {
  15.                 temp = num[i] + num[j] + num[k];
  17.                 if (abs(target - result) > abs(target - temp))
  18.                     result = temp;
  19.                 if (result == target)
  20.                     return result;
  21.                 ( temp > target ) ? --k : ++j;
  22.             }
  23.         }
  24.         return result;
  25.     }
  26. };

源码分析

和前面3Sum解法相似，同理使用i,j,k三个指针进行循环。

区别在于3sum中的target为0，这里新增一个变量用于比较哪组数据与target更为相近

复杂度分析

时间复杂度同理为O(n^2)
运行时间 16ms

Reference