【LeetCode】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.

题意：找出数组中所有和为0的不同的三个数，从小到大排列

思路：

刚开始想用双指针，然后在两个指针中间去找第三个数，但是想不到边上的两个指针往中间递进的条件。

然后就只有先确定一个数，然后用双指针去找另外两个数

 1 class Solution(object):
 2     def threeSum(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: List[List[int]]
 6         """
 7         l = len(nums)
 8         if l<3:
 9             return []
10         res = []
11         nums.sort()
12         i=0
13         while(i<l-2):
14             if nums[i]>0:
15                 break;
16             target = 0 - nums[i]
17             start = i+1;end = l-1
18             while start<end:
19                 tmp = nums[start] + nums[end]
20                 if tmp>target:
21                     end-=1
22                 elif tmp<target:
23                     start+=1
24                 else:
25                     res.append([nums[i],nums[start],nums[end]])
26                     t = start
27                     while start<end and nums[t]==nums[start]:　　　　　　#略过相同的数
28                         start+=1
29                     t = end
30                     while start<end and nums[t]==nums[end]:　　　　　　　　#略过相同的数
31                         end-=1
32             t=i
33             while i<l-2 and nums[t]==nums[i]:
34                 i+=1
35         return res

.。。终于想到了，可以用双指针，用二分法找第三个值，但是要用到递归

。。。但是这种方法没ac，因为递归生成输出的结果。。。。有重复，这个题够折磨了，先到这吧

 1 class Solution(object):
 2     def threeSum(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: List[List[int]]
 6         """
 7         l = len(nums)
 8         if l<3:
 9             return []
10         res = []
11         nums.sort()
12         start=0;end=l-1
13         flag=0
14         while start<end-1:
15             tmp = nums[start]+nums[end]
16             target = 0-tmp
17             mid = (start+end)//2
18             tstart=start;tend=end
19             while tstart<mid<tend and nums[tstart]<=target<=nums[tend]:
20                 if nums[mid]==target:
21                     flag=1
22                     res.append([nums[start],nums[mid],nums[end]])
23                     break
24                 elif nums[mid]>target:
25                     t=mid
26                     mid=(tstart+mid)//2
27                     tend=t
28                 else:
29                     t = mid
30                     mid=(mid+tend)//2
31                     tstart=t
32             if flag==1:
33                 flag=0
34                 
35                 subnums=self.threeSum(nums[start:end])
36                 if subnums!=[]:
37                     for x in subnums:
38                         res.append(x)
39                 
40                 subnums=self.threeSum(nums[start+1:end+1])
41                 if subnums!=[]:
42                     for x in subnums:
43                         res.append(x)
44                             
45                 t=start
46                 while start<end and nums[t]==nums[start]:
47                     start+=1
48                 t=end
49                 while start<end and nums[t]==nums[end]:
50                     end-=1
51             else:
52                 if tmp<0:
53                     start+=1
54                 else:
55                     end-=1
56         
57         return res