3 Sum Closest

Question

  • leetcode: 3Sum Closest | LeetCode OJ

  • lintcode: (59) 3 Sum Closest

    1. Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target.
      1. Return the sum of the three integers. You may assume that each input would have exactly one solution.
        1. For example, given array S = {-1 2 1 -4}, and target = 1.
      3. 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
    12.   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
    25.   26.             while (start < end):
    27.                 sum3 = numbers[start] + numbers[end] + item_i
    28.                 if abs(sum3 - target) < abs(result - target):
    29.                     result = sum3
    30.   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
    45.   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());
    7.   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];
    16.   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

  • 3Sum Closest | 九章算法