首页 > 代码库 > 【LeetCode】15. 3Sum

【LeetCode】15. 3Sum

2024-08-28 17:12:47   216人阅读

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

 

【LeetCode】15. 3Sum


联系
我们