Leetcode#015-HOT-三数之和 • Liu Yang's Blog

读题

一个nums列表，nums中数字重复，要求给出nums中有没有三个索引不同值的组合，每个组合的三数之和为0。

思路

设数组总长度为n, 可以先给数组排好序, 这样可以避免之后去重.

使用双指针算法，然后从小到大开始遍历，遍历的元素假设为组合中的最小值，索引为i

则双指针l和r可设置为i+1, n-1

若三个数的组合小于0，则表示左指针小了，右移

若三个数的组合大于0，则表示右指针大了，左移

当两个指针相遇，即l>=r，则无解，此时可跳过

遍历元素和指针若发现相同的元素，都应该移动，来避免重复。

实现

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        check = lambda a,b,c :(nums[a] + nums[b] + nums[c])
        n, ans = len(nums), []
        if n < 3: return []
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]: continue
            l, r = i + 1, n - 1
            while l < r:
                temp = check(i,l,r)
                if temp == 0:
                    ans.append([nums[i], nums[l], nums[r]])
                    # 跳过重复的 l 和 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
                elif temp < 0:l += 1
                else: r -= 1
        return ans