三数之和怎么求？LeetCode 15、16 题记

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/3sum

# lst 为和为 0 的三元组
lst = [num_sort[i],num_sort[x],num_sort[y]]
# result 为结果列表，先判断是否包含该 lst，若没有再添加到结果中
if lst not in result:
    result.append(lst)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 为了方便指针定位以及对三元处理，现将数组列表排序
        num_sort = sorted(nums)
        # 获取列表长度
        l = len(num_sort)
        # result 列表用来保存三元组结果
        result=[]
        # 三元组中的第一位用i来表示，它之后还有两元，故最大值 l-3
        for i in range(l-2):
            # x 和 y 是双指针，一个略大于 i，一个在最大边界 l-1
            x,y = i+1,l-1
            # 若整个列表最小值大于0，则全部都大于0；若最大值小于0，则全为负
            if num_sort[i]>0 or num_sort[y]<0:
                # 以上情况不会出现和为 0 的三元组，直接返回空列表
                return result
            # 这里用来对第一元去重，如果新拿到的 i 值和上一轮 i 值相同，直接跳过本次循环后续内容
            if i>0 and num_sort[i]==num_sort[i-1]:
                continue
            # while 循环开启双指针的缩小范围
            while x < y:
                # 计算三元组的和
                temp = num_sort[i] + num_sort[x] + num_sort[y]
                # 如果和小于 0 ，为了得到和为 0 ，需要增加值，移动 x 指针
                if temp<0:
                    x += 1
                # 如果和大于 0，为了缩小到 0，需要减少值，移动 y 指针
                elif temp>0:
                    y -= 1
                # 如果和为0
                else:
                    # 记录三元组
                    lst = [num_sort[i],num_sort[x],num_sort[y]]
                    # 结果中添加三元组
                    result.append(lst)
                    # 检测 x 之后的值是否与 x 相同，若是，通过 while 循环提高 x 的值到最后一个重复值
                    while x<y and num_sort[x+1]==num_sort[x]:
                        x += 1
                    # 检测 y 之前的值是否与 y 相同，若是，通过 while 循环缩减 y 的值到第一个重复值
                    while x<y and num_sort[y-1]==num_sort[y]:
                        y -=1
                    # 此时统一对 x 和 y 移动寻找下一组三元组
                    x += 1
                    y -= 1 
        # 整个 for 循环完成后，将记录结果的列表返回       
        return result

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/3sum-closest

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 刚用 sorted，这里用 sort 来进行排序
        nums.sort()
        l = len(nums)
        # dic 字典储存求和值对应的三数情况
        dic = {}
        # 三数中第一个用 i 来定位
        for i in range(l-2):
            # 双指针 x 和 y，左侧指针略大于 i，右侧指针在右侧边界
            x,y = i+1,l-1
            # while 循环来缩小双指针范围
            while x<y:
                # 三数求和
                temp = nums[i]+nums[x]+nums[y]
                # 将求和值和对应三个数组成的列表存储到字典中
                dic[temp] = [nums[i],nums[x],nums[y]]
                # 若和小于 target，为了更靠近，右移左侧指针增加和
                if temp < target:
                    x+=1
                # 若和大于 target，移动右侧指针
                elif temp >target:
                    y-=1
                # 若和为 target，提前结束返回
                else:
                    return target
        # 若执行完整个 for 循环，我们得到了双指针法求和结果的字典
        # 获取字典的 keys() 即求和值的列表，先排序
        target_key = sorted(list(dic.keys()))
        # 计算排序后第一位与 target 差值的绝对值
        target_min = abs(target - target_key[0])
        # result 用来记录返回结果
        result = 0
        # 对排序后的求和值列表进行遍历
        for i,n in enumerate(target_key):
            # 对每个求和值进行运算，求它们与 target 差值的绝对值
            tmp = abs(n-target)
            # 找最小的差值，即最接近 target
            target_min = min(target_min,tmp)
            # 如果此位置恰好满足更小的情况，将此时求和值赋值给 result
            if target_min == tmp:
                result = n
        # 经过遍历，把差值最小时的求和值已经赋值给 result了，最终返回            
        return result

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:        
        nums.sort()
        l = len(nums)
        # result 默认为无穷大
        result = float("inf")
        # 双指针法来表示三个数
        for i in range(l-2):
            x,y = i+1,l-1
            # 对 x 和 y 双指针进行处理
            while x<y:
                # temp 为此时三数的和
                temp = nums[i]+nums[x]+nums[y]
                if temp < target:
                    x+=1
                elif temp >target:
                    y-=1
                else:
                    return target
                # 如果此时和与 target 差值更小，则保存此求和到 result 中
                if abs(temp - target) < abs(result-target):
                    result = temp   
        return result