LeetCode 15: 3Sum题解（python）

Leetcode 42: Trapping Rain Water

分类：Two pointers

难度：M

描述：给了一个数组，问数组中存不存在a, b, c三个元素，使a + b + c = 0。把这些数组都找出来。

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

链接: 3Sum.

思路：

本题使用双指针法，遍历数组，然后每次遍历中使用前后指针搜索是否存在满足条件的a, b, c。这个题有两个点需要注意：
1）排序。一定要先排序
2）重复元素处理。如果遇到重复的元素怎么办？在左右指针判断完记录后，可以略过重复项。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums or len(nums) < 3:  判断边界条件
            return []
        nums = sorted(nums)
        res = []
        i = 0
        while i < len(nums):  此处用while循环是为了便于略过重复项。
            left = i + 1
            right = len(nums) - 1
            summ = -nums[i]
            while left < right:
                if nums[left] + nums[right] == summ:
                    temp = [nums[i], nums[left], nums[right]] 记录
                    res.append(temp)
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    while left < right and nums[right] == nums[right+1]:
                        right -= 1  两处while循环用于略过左右指针的重复项。
                elif nums[left] + nums[right] < summ:
                    left += 1
                else:
                    right -= 1
                while i < len(nums) - 1 and nums[i] == nums[i+1]: 略过重复项。
                    i += 1
        
            i += 1 不可忽略i的自增

        return res

个人总结：

1）本题有许多类似题型，如：16，18，259，611.
2）本题比较麻烦的地方在于重复项的处理。
2）双指针的题，大多数是两重循环（for + while）。除此之外，注意是否需要先排序。

本文地址：https://blog.csdn.net/Bourns_A/article/details/107358375