16. 3Sum Closest，最接近目标的三数和

Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        size = len(nums)
        if size == 3:
            return nums[0]+nums[1]+nums[2]
        nums.sort()
        s = nums[0]+nums[1]+nums[2]
        if s >= target:
            return s
        s = nums[size-3]+nums[size-2]+nums[size-1]
        if s <= target:
            return s 
        """
        nums.sort()
        size = len(nums)
        if size == 3:
            return sum(nums)
        if (d:=sum(nums[:3])) >= target:
            return d
        if (d:=sum(nums[-3:])) <= target:
            return d
        """
        dsmin = (0xFFFFFFFF,0)
        for i in range(size-2):
            t = target - nums[i]
            if (nums[i]>=0
                    and target<=nums[i]
                    and abs(t)*3>=dsmin[0]):
                break
            left = i + 1
            right = size - 1
            while left < right:
                s = nums[left] + nums[right]
                if s == t:
                    return target
                d = abs(s-t)
                if d < dsmin[0]:
                    dsmin = (d, s+nums[i])
                if s < t:
                    left += 1
                else:
                    right -= 1
        return dsmin[1]

$ python -m timeit -s 'a=[i for i in range(3)]' -p 'sum(a[:3])'
1000000 loops, best of 5: 230 nsec per loop
$ python -m timeit -s 'a=[i for i in range(3)]' -p 'a[0]+a[1]+a[2]'
5000000 loops, best of 5: 99 nsec per loop
$ python -m timeit -s 'a=[i for i in range(1000)]' -p 'sum(a[:3])'
1000000 loops, best of 5: 222 nsec per loop
$ python -m timeit -s 'a=[i for i in range(1000)]' -p 'a[0]+a[1]+a[2]'
2000000 loops, best of 5: 128 nsec per loop

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        size_t size {nums.size()};
        /*if(size == 3)
            return accumulate(nums.begin(),nums.end(),0);
        int s { accumulate(nums.begin(),nums.begin()+3,0) };
        if(s >= target)
            return s;
        s = accumulate(nums.end()-3, nums.end(), 0);
        if(s <= target)
            return s;*/
        int s { nums[0]+nums[1]+nums[2] };
        if(size==3 || s>=target)
            return s;
        s = nums[size-3]+nums[size-2]+nums[size-1];
        if(s <= target)
            return s;
        pair<int,int> dsmin { 0x7FFFFFFF, 0 };  //!! cannot be 0xFFFFFFFF
        for(size_t i{}; i<size-2; ++i){
            int t { target-nums[i] };
            if(nums[i]>=0
                    && target<=nums[i]
                    && abs(t)*3>=dsmin.first)
                break;
            size_t left { i+1 };
            size_t right { size-1 };
            while(left < right){
                s = nums[left] + nums[right];
                if(s == t)
                    return target;
                int d { abs(s-t) };
                if(d < dsmin.first){
                    dsmin.first = d;
                    dsmin.second = s+nums[i];
                }
                if(s < t)
                    ++left;
                else
                    --right;
            }
        }
        return dsmin.second;
    }
};

static int comp(const void *a, const void *b){
    // no overflow according to constraints
    return *(int*)a - *(int*)b;
}

int threeSumClosest(int* nums, int numsSize, int target){
    if(numsSize == 3)
        return nums[0]+nums[1]+nums[2];
    qsort(nums, numsSize, sizeof(int), comp);
    int s = nums[0]+nums[1]+nums[2];
    if(s >= target)
        return s;
    s = nums[numsSize-3]+nums[numsSize-2]+nums[numsSize-1];
    if(s <= target)
        return s;
    int diff = 0x7FFFFFFF;
    int sum = 0;
    for(int i=0; i<numsSize-2; ++i){
        int t = target - nums[i];
        if(nums[i]>=0 && target<=nums[i] && abs(t)*3>=diff)
            break;
        int left = i + 1;
        int right = numsSize - 1;
        while(left < right){
            s = nums[left] + nums[right];
            if(s == t)
                return target;
            int d = abs(s-t);
            if(d < diff){
                diff = d;
                sum = s + nums[i];
            }
            if(s < t)
                ++left;
            else
                --right;
        }
    }
    return sum;
}