# 3 Sum ### Source - leetcode: [3Sum | LeetCode OJ](https://leetcode.com/problems/3sum/) - lintcode: [(57) 3 Sum](http://www.lintcode.com/en/problem/3-sum/) ~~~ Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Example For example, given array S = {-1 0 1 2 -1 -4}, A solution set is: (-1, 0, 1) (-1, -1, 2) Note Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. ~~~ ### 題解1 - 排序 + 哈希表 + 2 Sum 相比之前的 [2 Sum](http://algorithm.yuanbin.me/zh-cn/integer_array/2_sum.html), 3 Sum 又多加了一個數，按照之前 2 Sum 的分解為『1 Sum + 1 Sum』的思路，我們同樣可以將 3 Sum 分解為『1 Sum + 2 Sum』的問題，具體就是首先對原數組排序，排序后選出第一個元素，隨后在剩下的元素中使用 2 Sum 的解法。 ### Python ~~~ class Solution: """ @param numbersbers : Give an array numbersbers of n integer @return : Find all unique triplets in the array which gives the sum of zero. """ def threeSum(self, numbers): triplets = [] length = len(numbers) if length < 3: return triplets numbers.sort() for i in xrange(length): target = 0 - numbers[i] # 2 Sum hashmap = {} for j in xrange(i + 1, length): item_j = numbers[j] if (target - item_j) in hashmap: triplet = [numbers[i], target - item_j, item_j] if triplet not in triplets: triplets.append(triplet) else: hashmap[item_j] = j return triplets ~~~ ### 源碼分析 1. 異常處理，對長度小于3的直接返回。 1. 排序輸入數組，有助于提高效率和返回有序列表。 1. 循環遍歷排序后數組，先取出一個元素，隨后求得 2 Sum 中需要的目標數。 1. 由于本題中最后返回結果不能重復，在加入到最終返回值之前查重。 由于排序后的元素已經按照大小順序排列，且在2 Sum 中先遍歷的元素較小，所以無需對列表內元素再排序。 ### 復雜度分析 排序時間復雜度 O(nlogn)O(n \log n)O(nlogn), 兩重`for`循環，時間復雜度近似為 O(n2)O(n^2)O(n2)，使用哈希表(字典)實現，空間復雜度為 O(n)O(n)O(n). 目前這段源碼為比較簡易的實現，leetcode 上的運行時間為500 + ms, 還有較大的優化空間，嗯，后續再進行優化。 ### C++ ~~~ class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int> > result; if (num.size() < 3) return result; int ans = 0; sort(num.begin(), num.end()); for (int i = 0;i < num.size() - 2; ++i) { if (i > 0 && num[i] == num[i - 1]) continue; int j = i + 1; int k = num.size() - 1; while (j < k) { ans = num[i] + num[j] + num[k]; if (ans == 0) { result.push_back({num[i], num[j], num[k]}); ++j; while (j < num.size() && num[j] == num[j - 1]) ++j; --k; while (k >= 0 && num[k] == num[k + 1]) --k; } else if (ans > 0) --k; else ++j; } } return result; } }; ~~~ ### 源碼分析 同python解法不同，沒有使用hash map ~~~ S = {-1 0 1 2 -1 -4} 排序后： S = {-4 -1 -1 0 1 2} ↑ ↑ ↑ i j k → ← i每輪只走一步，j和k根據S[i]+S[j]+S[k]=ans和0的關系進行移動，且j只向后走（即S[j]只增大），k只向前走（即S[k]只減小） 如果ans>0說明S[k]過大，k向前移；如果ans<0說明S[j]過小，j向后移；ans==0即為所求。 至于如何取到所有解，看代碼即可理解，不再贅述。 ~~~ ### 復雜度分析 外循環i走了n輪,每輪j和k一共走n-i步，所以時間復雜度為O(n2)O(n^2)O(n2)。最終運行時間為52ms ### Reference - [3Sum | 九章算法](http://www.jiuzhang.com/solutions/3sum/) - [A simply Python version based on 2sum - O(n^2) - Leetcode Discuss](https://leetcode.com/discuss/32455/a-simply-python-version-based-on-2sum-o-n-2)