3 Sum

Question

  1. Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
  2. Find all unique triplets in the array which gives the sum of zero.
  4. Example
  5. For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:
  7. (-1, 0, 1)
  8. (-1, -1, 2)
  9. Note
  10. Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  12. The solution set must not contain duplicate triplets.

題解1 - 排序 + 哈希表 + 2 Sum

相比之前的 2 Sum, 3 Sum 又多加了一個數，按照之前 2 Sum 的分解為『1 Sum + 1 Sum』的思路，我們同樣可以將 3 Sum 分解為『1 Sum + 2 Sum』的問題，具體就是首先對原陣列排序，排序後選出第一個元素，隨後在剩下的元素中使用 2 Sum 的解法。

Python

  1. class Solution:
  2.     """
  3.     @param numbersbers : Give an array numbersbers of n integer
  4.     @return : Find all unique triplets in the array which gives the sum of zero.
  5.     """
  6.     def threeSum(self, numbers):
  7.         triplets = []
  8.         length = len(numbers)
  9.         if length < 3:
  10.             return triplets
  12.         numbers.sort()
  13.         for i in xrange(length):
  14.             target = 0 - numbers[i]
  15.             # 2 Sum
  16.             hashmap = {}
  17.             for j in xrange(i + 1, length):
  18.                 item_j = numbers[j]
  19.                 if (target - item_j) in hashmap:
  20.                     triplet = [numbers[i], target - item_j, item_j]
  21.                     if triplet not in triplets:
  22.                         triplets.append(triplet)
  23.                 else:
  24.                     hashmap[item_j] = j
  26.         return triplets

源碼分析

  1. 異常處理，對長度小於3的直接返回。
  2. 排序輸入陣列，有助於提高效率和返回有序列表。
  3. 循環遍歷排序後陣列，先取出一個元素，隨後求得 2 Sum 中需要的目標數。
  4. 由於本題中最後返回結果不能重複，在加入到最終返回值之前查重。

由於排序後的元素已經按照大小順序排列，且在2 Sum 中先遍歷的元素較小，所以無需對列表內元素再排序。

複雜度分析

排序時間複雜度 O(n \log n), 兩重for循環，時間複雜度近似為 O(n^2)，使用哈希表(字典)實現，空間複雜度為 O(n).

目前這段源碼為比較簡易的實現，leetcode 上的運行時間為500 + ms, 還有較大的優化空間，嗯，後續再進行優化。

C++

  1. class Solution {
  2. public:
  3.     vector<vector<int> > threeSum(vector<int> &num) 
  4.     {
  5.         vector<vector<int> > result;
  6.         if (num.size() < 3) return result;
  8.         int ans = 0;
  10.         sort(num.begin(), num.end());
  12.         for (int i = 0;i < num.size() - 2; ++i)
  13.         {
  14.             if (i > 0 && num[i] == num[i - 1])  
  15.                 continue;
  16.             int j = i + 1;
  17.             int k = num.size() - 1;
  19.             while (j < k)
  20.             {
  21.                 ans = num[i] + num[j] + num[k];
  23.                 if (ans == 0)
  24.                 {
  25.                     result.push_back({num[i], num[j], num[k]});
  26.                     ++j;
  27.                     while (j < num.size() && num[j] == num[j - 1])
  28.                         ++j;
  29.                     --k;
  30.                     while (k >= 0 && num[k] == num[k + 1])
  31.                         --k;
  32.                 }
  33.                 else if (ans > 0) 
  34.                     --k;
  35.                 else 
  36.                     ++j;
  37.             }
  38.         }
  40.         return result;
  41.     }
  42. };

Java

  1. public class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         // Assumptions: array is not null, array.length >= 3
  4.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  5.         Arrays.sort(nums);
  6.         for (int i = 0; i < nums.length - 2; i++) {
  7.             if (i > 0 && nums[i] == nums[i - 1]) {
  8.                 continue;
  9.             }
  10.             int left = i + 1;
  11.             int right = nums.length - 1;
  12.             while (left < right) {
  13.                 int tmp = nums[left] + nums[right];
  14.                 if (tmp + nums[i] == 0) {
  15.                     result.add(Arrays.asList(nums[i], nums[left], nums[right]));
  16.                     left++;
  17.                     while (left < right && nums[left] == nums[left - 1]) {
  18.                         left++;
  19.                     }
  20.                 } else if (tmp + nums[i] < 0) {
  21.                     left++;
  22.                 } else {
  23.                     right--;
  24.                 }
  25.             }
  26.         }
  27.         return result;
  28.     }
  29. }

源碼分析

同python解法不同，沒有使用hash map

  1. S = {-1 0 1 2 -1 -4}
  2. 排序後：
  3. S = {-4 -1 -1 0 1 2}
  4.       ↑  ↑        ↑
  5.       i  j        k
  6.          →        ←
  7. i每輪只走一步，j和k根據S[i]+S[j]+S[k]=ans和0的關係進行移動，且j只向後走（即S[j]只增大），k只向前走（即S[k]只減小）
  8. 如果ans>0說明S[k]過大，k向前移；如果ans<0說明S[j]過小，j向後移；ans==0即為所求。
  9. 至於如何取到所有解，看程式碼即可理解，不再贅述。

複雜度分析

外循環i走了n輪,每輪j和k一共走n-i步，所以時間複雜度為O(n^2)。
最終運行時間為52ms

Reference