leetcode16. 最接近的三数之和

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

O(n)=N^2

//cpp
/*
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. 
Return the sum of the three integers. 
You may assume that each input would have exactly one solution.
*/

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) 
    {
        sort(nums.begin(),nums.end());

        int result = 0;     //用于存储最后返回值

        int minGap = INT_MAX;   //初始化result与target之间相差为最大整数值
        
        int length = nums.size();   

        for(int i = 0; i < length - 1; i++)  //最外层的循环，固定a来使得3SUM转为2SUM问题
        {
            // a去重
            if (i != 0 && nums[i] == nums[i - 1]) continue; 

            int left = i + 1, right = length - 1;

            while (left < right) // 同时考虑b,c的变化
            {
                int temp_sum = nums[i] + nums[left] + nums[right];

                int gap = abs(temp_sum - target);   //对result与target之间的相差取绝对值

                if (gap < minGap)   //存储result与target之间的相差最小的a+b+c的和
                {
                    minGap = gap;
                    result = temp_sum;
                }

                if (temp_sum < target) left++;  //继续遍历找到更好地结果
                else right--;
            }
        }
        return result;
    }
};

# python3
class Solution:
    def threeSumClosest(self, num, target):
        num.sort()
        result = num[0] + num[1] + num[2]
        for i in range(len(num) - 2):
            # j, k = i+1, len(num) - 1
            j = i+1
            k = len(num) - 1
            while j < k:
                sum = num[i] + num[j] + num[k]
                if sum == target:
                    return sum
                if abs(sum - target) < abs(result - target):
                    result = sum
                if sum < target:
                    j += 1
                elif sum > target:
                    k -= 1
        return result