題目：

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] ]
代碼：
題目意思很簡單：從數(shù)組中挑出三個數(shù)字，相加和為0，返回所有滿足條件的結果:
第一反應，當然是遍歷3次，吭哧吭哧寫完了：
??? def threeSum(self, nums):
??????? """
??????? :type nums: List[int]
??????? :rtype: List[List[int]]
??????? """
??????? nums.sort()
??????? result = []
??????? for x in range(0,len(nums)-2):????
??????????? for i in range(x+1,len(nums)-1):
??????????????? #print(i,nums[i],result)
??????????????? #if self.judge(nums[i],result):continue
??????????????? for j in range(i+1,len(nums)):
??????????????????? #if self.judge(nums[j],result):continue
??????????????????? if(nums[x]+nums[i]+nums[j]==0):
??????????????????????? if [nums[x],nums[i],nums[j]] not in result:
??????????????????????????? result.append([nums[x],nums[i],nums[j]])???????????????????
??????? return result
但是，問題來了，LeetCode提交測試會超時，測試數(shù)據(jù)是一串126個元素的數(shù)組，并且有120組符合條件的答案。
這種遍歷的方法試了一下，大概需要0.36s，確實不快，必定時間復雜度有O（n^3）了
想啊想，試了很多種，都不行，只能百度了一下大神算法，一時，只用了0.003秒，而且準確的說，除去枚舉第一個數(shù)之外，其余只需要遍歷一遍：
總共的時間復雜度不到：O（n^2）
拷貝過來記錄，并共大家參考學習：
??? def threeSum2(self, nums):
??????? '''
??????????? 題意：求數(shù)列中三個數(shù)之和為0的三元組有多少個，需去重
??????????? 暴力枚舉三個數(shù)復雜度為O(N^3)
??????????? 先考慮2Sum的做法，假設升序數(shù)列a，對于一組解ai,aj, 另一組解ak,al
??????????? 必然滿足 i<k j>l 或 i>k j<l, 因此我們可以用兩個指針，初始時指向數(shù)列兩端
??????????? 指向數(shù)之和大于目標值時，右指針向左移使得總和減小，反之左指針向右移
??????????? 由此可以用O(N)的復雜度解決2Sum問題，3Sum則枚舉第一個數(shù)O(N^2)
??????????? 使用有序數(shù)列的好處是，在枚舉和移動指針時值相等的數(shù)可以跳過，省去去重部分
??????? '''???????
??????? nums.sort()
??????? res = []
??????? length = len(nums)
??????? for i in range(0, length - 2):
??????????? if i and nums[i] == nums[i - 1]:
??????????????? continue
??????????? target = nums[i] * -1
??????????? left, right = i + 1, length - 1
???????????
　　　　　　　while left < right:
??????????????? if nums[left] + nums[right] == target:
??????????????????? res.append([nums[i], nums[left], nums[right]])
??????????????????? right -= 1
??????????????????? left += 1
??????????????????? while left < right and nums[left] == nums[left - 1]:
??????????????????????? left += 1
??????????????????? while left < right and nums[right] == nums[right + 1]:
??????????????????????? right -= 1
??????????????? elif nums[left] + nums[right] > target:
??????????????????? right -= 1
??????????????? else:
??????????????????? left += 1
??????? return res???

轉載于:https://www.cnblogs.com/yuanzhaoyi/p/6032980.html

總結

以上是生活随笔為你收集整理的15. 3Sum_左右开工，遍历找出符合目标的数字的全部內容，希望文章能夠幫你解決所遇到的問題。

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