python最接近的三数之和

leetcode 16题
重点在于优化以避免重复

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        L = len(nums)
        minDiff = sum(nums[:3]) - target
        for i in range(L):
            if i and nums[i] == nums[i-1]: continue #第一个数相等则跳过
            a = nums[i]
            midTarget = target - a
            b, c = i+1, L-1 #去除重复，剩余两数范围为[i+1,L-1]
            while b < c:
                diff = nums[b]+nums[c] - midTarget
                if diff == 0: 
                    return target          
                minDiff = diff if abs(diff) < abs(minDiff) else minDiff
                if diff < 0:
                    b += 1 #left移动一次
                    while b < c and nums[b] == nums[b-1]: b += 1#相等则继续移动
                else:
                    c -= 1 #right移动一次
                    while b < c and nums[c] == nums[c+1]: c -= 1#相等则继续移动 
        return target + minDiff

相似题目：leetcode 18题 四数之和

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        L = len(nums)
        res = []
        if L <4: return res
        nums = sorted(nums)
        if sum(nums[:4]) > target or sum(nums[-4:] ) < target: return res
        for i in range(L-3):
            if i and nums[i] == nums[i-1]: continue
            if sum(nums[i:i+4]) > target: return res
            if sum(nums[-3:]) < (target-nums[i]): continue
            a = nums[i]
            for j in range(i+1,L-2):
                if j > i+1 and nums[j] == nums[j-1]: continue
                if sum(nums[-2:]) < (target-a-nums[j]):continue
                if sum(nums[j:j+3]) > (target-a): break
                b = nums[j]
                p,q = j+1, L-1
                while p < q:
                    c,d = nums[p], nums[q]
                    diff = (a+b+c+d) - target 
                    if not diff: 
                        res.append([a,b,c,d])
                        p += 1
                        q -= 1
                        while p < q and nums[p] == nums[p-1]: p += 1
                        while p < q and nums[q] == nums[q+1]: q -= 1
                    elif diff <0: 
                        p += 1
                        while p < q and nums[p] == nums[p-1]: p += 1
                    else: 
                        q -= 1
                        while p< q and nums[q] == nums[q+1]: q -= 1    
        return res