前往此题

排序 + 双指针

创建三指针k,i,j, i, j分别指向数组的头和尾，k指向遍历过的最小值

其中有几个点需要考虑

1. 既然其中有一个条件是无重复，那么优先想到的是对数组进行排序
2. 排序后nums[k]必然是小于0的，因为nums[i] 和nums[j]都大于nums[k]
3. 如何过滤重复值？
   1. 在遇到符合条件的情况下，k不动，i, j更改指针
   2. 其他情况下为了避免计算重复值，i, j在遇到重复值直接跳过
   3. 当调整指针k的时候，同样需要避免重复，如遇到nums[k] == nums[k-1]则需要跳过
4. 接着循环计算调整i , j,
   1. 如果nums[k] + nums[i] + nums[j] > 0, j -= 1来跳过重复元素
   2. 如果nums[k] + nums[i] + nums[j] < =, i += 1来跳过重复元素

代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res, k = [], 0

        for k in range(len(nums) - 2):
            if nums[k] > 0: break
            if k > 0 and nums[k] == nums[k-1]: continue
            i, j = k + 1, len(nums) - 1
            while i < j:
                s = nums[k] + nums[i] + nums[j]
                if s == 0:
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i-1]: i += 1
                    while i < j and nums[j] == nums[j+1]: j -= 1
                elif s < 0:
                    i += 1
                    while i < j and nums[i] == nums[i-1]: i += 1
                else:
                    j -= 1
                    while i < j and nums[j] == nums[j+1]: j -= 1
        return res