leetcode_15

发表于   |   分类于

3Sum

题目戳这

题意

给一个数组，输出所有三个数的组合，使得a+b+c=0，且没有重复的(比如[1, 2, 3], [3, 1, 2]就是算重复的)。

解法

为了防止过多的重复，我们先将整个数组进行排序，然后我用 mp[x]来记录x出现在数组中的最靠右边的位置，这样尽量使得a+b+c=0中的a, b, c是递增的，假如最靠右边的b的位置还是小于c的，那么我们就不要这个组合。枚举的过程中只要枚举两个数即可，第三个数我们用mp[]来观察是否存在。最后再去一次重复即可。

代码

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
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        mp = {}
        nums.sort()
        for i in range(len(nums)):
            if nums[i] not in mp: 
                mp[nums[i]] = i
            mp[nums[i]] = i  # 记录最靠的位置
        
        res = []
        for i in range(len(nums)):
            if i and nums[i] == nums[i-1]: # 如果有重复的，则就不需要枚举
                continue
            for j in range(i+1, len(nums)):
                sm = nums[i] + nums[j]
                sm = 0-sm
                if sm in mp and mp[sm] > j: # 观察sm的值是否存在在mp数组中，且其位置是最右边的
                    res.append([nums[i], nums[j], sm])
        res1 = []
        for x in res:
            if x not in res1:
                res1.append(x)
        return res1