一、題目

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:

• 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.

?

For example, given array S = {-1 0 1 2 -1 -4},A solution set is:(-1, 0, 1)(-1, -1, 2)

二、思路
我的思路一直很簡單，當初在做2Sum的時候，就是把求和問題變成了一個查找問題，定下一個數a，去找target-a在不在剩余的數里。3Sum也這么做，但是效率明顯低多了。而且這題讓輸出所有可能的答案組合，牽扯到重復的問題。
做法還是按照變求和為查詢，定下a,b，找target-(a+b)，唯一做的優化就是用哈希表存下已有的（a,b），這樣不至于做重復的查找。但是這樣畢竟不是辦法，以后做4sum就要4層循環了，不是個事。看別人的答案，是從兩邊往中間找，這個挺好的。準備在3Sum Closet里試一下這種方法。

三、代碼 1 class Solution: 2 # @param {integer[]} nums 3 # @return {integer[][]} 4 def threeSum(self, nums): 5 nums.sort() 6 passed_list = [] 7 result = [] 8 record = {} 9 result_dict = {} 10 if len(nums) < 3: 11 return [] 12 else: 13 for i in range(len(nums)): 14 for j in range(i + 1, len(nums)): 15 a = nums[i] 16 b = nums[j] 17 if (a, b) in record: 18 pass 19 else: 20 record[(a, b)] = 0 21 target = 0 - a - b 22 if target in nums[j + 1:]: 23 passed_list.append(a) 24 passed_list.append(b) 25 passed_list.append(target) 26 if str(passed_list) in result_dict: 27 passed_list = [] 28 pass 29 else: 30 result.append(passed_list) 31 result_dict[str(passed_list)] = 0 32 passed_list = [] 33 return result

?

四、總結

準備把n-sum這類問題全部做完，然后總結一下這類題的規律。

轉載于:https://www.cnblogs.com/breada/p/4761906.html

總結

以上是生活随笔為你收集整理的[LeetCode]#13 3sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。