3sum跟之前的2sum有点像,但难度更大一些

leetcode.15

题目描述 :

1
2
3
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

范围0 <= nums.length <= 3000

方法1:

枚举所有方法,时间复杂度n^3,会超时

方法2:

排序

哈希法(2等1)

循环i,j 此时 t=0-nums[i]-nums[j]

根据哈希,判断t是否在数组中出现过

注意:需要去重

方法3:

排序

双指针(1等2)

t=0-nums[i]-nums[j]

思路:

固定i指针,j,k分别在两端,交替向中间靠拢(比较t)

注意:去重

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #双指针移动
        #i为定指针
        #j,k为移动指针
        #首先要排序
        nums.sort()        
        lens=len(nums)
        
        res=[]
        for i in range(lens):
            
            #要求j,k位置的和
            #对第一个位置要特殊判断
            if i and nums[i]==nums[i-1]:
                continue
            j=i+1
            k=lens-1
            tmp=0-nums[i]
            while(j<k):
                arr=[]
                if nums[j]+nums[k]>tmp:
                    k=k-1
                elif nums[j]+nums[k]<tmp:
                    j=j+1
                else:
                    #添加数组元素的另一种方法:
                    #res.append([nums[i],nums[L],nums[R]])
                    arr.append(nums[i])
                    arr.append(nums[j])
                    arr.append(nums[k])
                    
                    res.append(arr)
                    #此处直接去重
                    while((j<k) and nums[j]==nums[j+1]):
                        j=j+1
                    while((j<k) and nums[k]==nums[k-1]):
                        k=k-1
                    k=k-1
                    j=j+1
        return res

小结

此题题目简单,但是需要考虑的东西也比较细.

  • 去重
  • hash及set的使用
  • 双指针
  • 剪枝
  • 对首位的特殊判断