0015._3Sum.md

Links:

1. https://leetcode.com/problems/3sum/
2. https://leetcode-cn.com/problems/3sum/

Tags

1. 数组
2. 双指针

Solution 1 超时:

1. 化为n个2Sum问题(leetcode 第一题)
2. 遍历列表，第 i 个子问题中的 target 为 -nums[i]
3. 往后找两个数的和为target

时间复杂度，因为2Sum: O(n) 所以3Sum=n*2Sum: O(n^2)

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        for i, current_num in enumerate(nums):
            target = -current_num
            memo = {}
            for next_num in nums[i+1:]:
                if next_num not in memo:
                    memo[target-next_num] = next_num
                else:
                    temp_ans = [current_num, memo[next_num], next_num]
                    temp_ans.sort()  # 避免重复
                    if temp_ans not in ans:
                        ans.append(temp_ans)

        return ans

---

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        nums.sort() 
        previous_num = None
        for i, current_num in enumerate(nums):
            if current_num == previous_num:
                continue
            target = -current_num
            memo = {}
            for next_num in nums[i+1:]:
                if next_num not in memo:
                    memo[target-next_num] = next_num
                else:
                    temp_ans = [current_num, memo[next_num], next_num]
                    if temp_ans not in ans: # 因为之前sort了，所以加上这句可以避免重复
                        ans.append(temp_ans)

            previous_num = current_num
        return ans

Solution 2 通过

排序 + 双指针。其实思想和Solution1一样，都是化为n个2Sum问题，不同的是在解决2Sum问题时不一样。 Solution1用查表来解决，Solution2用双指针解决。 另外，双指针比较灵活，很容易就解决答案重复问题。

1. 遍历列表，然后用双指针在当前数字的后面找组合，三个数相加为0即为其中一个答案。

class Solution:
    def threeSum(self, nums):
        res = []
        nums.sort()
        for i in range(len(nums)-2): 
            if i > 0 and nums[i] == nums[i-1]:  # 从第二个元素开始避免重复。例如nums = [0, 0, 0]
                continue
            l, r = i+1, len(nums)-1
            while l < r: # 确保找出当前数字的所有结果
                total = nums[i] + nums[l] + nums[r] 
                if total < 0:
                    l +=1 
                elif total > 0:
                    r -= 1
                else:
                    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
        return res

Solution 3 最快的解法

核心等式为pos_num + target + neg_num = 0。

即target = 0 - pos_num - neg_num。

1. 用字典memo存储每个数字的频率
2. 然后用字典的key(自动去重)去构造两个列表，一个存储正数，一个存储负数
3. pos_num和neg_num可以从两个列表中取出，然后构建target。
4. 从memo中查找target是否存在。如果存在，则证明有三个数符合要求。（而且找到target的话，如果target和pos_num或者neg_num相同的话，则证明三个数中有两个数字是相同的。即memo中频率大于2的情况）。

class Solution(object):
    def threeSum(self, nums):
        memo = {}
        res = []
        for i in nums: 
            memo[i] = memo.get(i,0) + 1

        pos = [i for i in memo if i > 0]    # 因为是从字典的key构造，所以自动去重了
        neg = [i for i in memo if i < 0]

        if 0 in memo and memo[0] >= 3:  # 特殊case
            res.append([0,0,0])
            
        for pos_num in pos:
            for neg_num in neg:
                target = 0 - pos_num - neg_num  # because (target + pos_num + neg_num) == 0
                if target in memo:
                    if (target == pos_num or target == neg_num) and memo[target] >= 2:
                        res.append([pos_num, target, neg_num])
                    elif pos_num > target > neg_num:
                        res.append([pos_num, target, neg_num])
        return res

总结

所有的Solutions核心都是找三个数，符合a + b + c = 0。

在找的过程中，有两个不同的思维：

1. 固定一个值，找另外两个数字。 (Solution 1和2)
2. 用另外两个数字的表达式代表剩下的数字，找剩下的数字。(Solution 3)