题目描述
这道题给你一个数组，找到所有三个数加起来等于0的数字并存到List里。结果不能有重复三元组。
我的解法——hash+两层循环（未AC）
- 先将数组各个数字出现频数统计再存到dict里，再固定两个数，从dict中找第三个数。
- 复杂度O(n2)
- 结果：TLE
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
dic = {}
res = []
for num in nums:
if(dic.has_key(num)):
dic[num] += 1
else:
dic[num] = 1
length = len(nums)
for i in range(length):
dic[nums[i]] -= 1
for j in range(length):
if(i == j):
continue
dic[nums[j]] -= 1
if(-nums[i]-nums[j] in dic and dic[-nums[i]-nums[j]] != 0):
now = [nums[i],nums[j],-nums[i] - nums[j]]
now.sort()
res.append(now)
dic[nums[j]] += 1
dic[nums[i]] += 1
res_res = []
for re in res:
flag = False
for re_re in res_res:
if(re[0] == re_re[0] and re[1] == re_re[1] and re[2] == re_re[2]):
flag = True
break
if(flag == False):
res_res.append(re)
return list(res_res)
最优解法——排序+双指针
- **最优解法 **
- 先排序。外循环i纪录第一个数字，内循环采用2 pointer的方法，当sum>0，tail往左移，sum < 0,head往右移。碰到sum ＝ nums[i] + nums[head] + nums[tail]时，把三个数字存到list里，并把list存到最外面的list2里面。
- 用while进行去重，666666666666
- Beat 34.23%
- n2的时间。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
length = len(nums)
res = []
for i in range(length - 2):
if i > 0 and nums[i] == nums[i-1]: # 对第一个数去重
continue
l = i + 1
r = length - 1
while(l < r):
if(nums[l] + nums[r] == -nums[i]):
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
elif(nums[l] + nums[r] > -nums[i]):
r -= 1
elif(nums[l] + nums[r] < -nums[i]):
l += 1
return res