[leetcode algorithms]題目15

15. 3Sum

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.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],A solution set is:[ [-1, 0, 1], [-1, -1, 2]]

自己寫的代碼：

首先將數組排序，外層循環尋找三個數字中的最左數字，因為要求三個數字相加等於0，那麼最左的數字left一定是個非正數。內層循環有兩個任務，一是在字典中尋找right，二是不斷更新{right : left}這個字典，因為三個數相加等於零，實際上只需要確定兩個數就可以知道第三個數了。列表中有很多重複元素，通過last_mid和last_right來減少重複計算。最後運行時間1551 ms

class Solution: def threeSum(self, nums): nums = sorted(nums) n = len(nums) res = [] last_left = float(inf) i = 0 while i < n - 1 and nums[i] <= 0: left = nums[i] if left == last_left: i += 1 continue dic = {} max_right = -(left + nums[i + 1]) last_mid = float(inf) last_right = float(inf) j = i + 1 while j < n and nums[j] <= max_right: mid = right = nums[j] if right >= 0 and right != last_right and right in dic: val = dic[right] res.append([val, -(right + val), right]) last_right = right if left + mid <= 0 and mid != last_mid: key = -(left + mid) dic[key] = left last_mid = mid j += 1 last_left = left i += 1 return res

討論區的優秀代碼：

整體的思路差不多，內層循環用的還是2sum的思路，建立左右兩個坐標，讓兩個坐標不斷地靠近。

def threeSum(self, nums): res = [] nums.sort() for i in xrange(len(nums)-2): if i > 0 and nums[i] == nums[i-1]: continue l, r = i+1, len(nums)-1 while l < r: s = nums[i] + nums[l] + nums[r] if s < 0: l +=1 elif s > 0: r -= 1 else: res.append((nums[i], nums[l], nums[r])) while l < r and nums[l] == nums[l+1]: l += 1 while l < r and nums[r] == nums[r-1]: r -= 1 l += 1; r -= 1 return res

推薦閱讀：