三数之和 - 数组，双指针问题

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

暴力, 三重遍历

import copy

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        for x in nums:
            xnum = copy.deepcopy(nums)
            xnum.remove(x)
            for y in xnum:
                ynum = copy.deepcopy(xnum)
                ynum.remove(y)
                for z in ynum:
                    if x + y + z == 0:
                        if [x,y,z] in res or [x,z,y] in res or [y,x,z] in res or [y,z,x] in res or [z,x,y] in res or [z,y,x] in res:
                            pass
                        else:
                            res.append([x,y,z])
        return res

双指针法

遍历排序后数组：

• 若 nums[i]>0：
  因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
• 对于重复元素：
  跳过，避免出现重复解

令左指针 L=i+1，右指针 R=n-1，当 L<R时，执行循环：
当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解

• 若和大于 0，说明 nums[R] 太大，R 左移
• 若和小于 0，说明 nums[L] 太小，L 右移

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []
        if n < 3 or not nums:
            return []

        for i in range(n):
            if(nums[i] > 0):
                return res
            if(i>0 and nums[i] == nums[i-1]):
                continue

            L = i + 1
            R = n - 1
            while L < R:
                if nums[i]+nums[L]+nums[R] == 0:
                    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
                elif nums[i]+nums[L]+nums[R] > 0:
                    R -= 1
                else:
                    L += 1
        return res

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

nums = [-1，2，1，-4], target = 1.
与 target 最接近的三个数的和为 2.
-1 + 2 + 1 = 2

对 nums 排序
双指针法不断计算 sums 和 target 比较：
如果一致直接返回。
如果差值比之前存储的小就替换。
sums 比 target 小，左指针右移，增大左值
sums 比 target 大，右指针左移，减小右值

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if not sum or n<3:
            return []
        nums.sort()
        res = float('inf')
        for i in range(n):
            if i>0 and nums[i] == nums[i-1]:
                continue
            L = i+1
            R = n-1
            while L<R:
                cur_sum = nums[i] + nums[L] + nums[R]
                diff = cur_sum - target
                if diff == 0:
                    return target
                if abs(diff) < abs(res-target):
                    res = cur_sum
                if diff < 0:
                    L += 1
                    while L<R and nums[L] == nums[L-1]:
                        L+=1
                else:
                    R -= 1
                    while L<R and nums[R] == nums[R+1]:
                        R-=1
        return res