LeetCode 16.最接近的三数之和

16.最接近的三数之和

题目链接
题目分析
此题的思路与15.三数之和有些相似。都是固定一个点，剩余两个点使用双指针查找，为了使用双指针，首先要对原数组进行排序。

同时，为了方便运算，如果原数字有且仅有3个数字，直接返回其和。

if (nums.size() == 3) return nums[0] + nums[1] + nums[2];
sort(nums.begin(), nums.end());

然后就是教科书式的双指针遍历了，遍历起始值i，左指针left = i + 1，右指针right = nums.size() - 1，计算temp = nums[i] + nums[left] + nums[right]：

• 若temp == target，直接返回target；
• 若temp < target：
  • 计算temp与target差值，如果小于当前差值，则更新差值与res，左指针加一left++;
• 若temp > target：
  • 计算temp与target差值，如果小于当前差值，则更新差值与res，右指针减一right--;

最后返回res。

遍历过程：

int del = INT_MAX;
int res;
for (int i = 0; i < nums.size() - 2; i++) {
    int l = i + 1;
    int r = nums.size() - 1;
    int temp = nums[i] + nums[l] + nums[r];
    if (temp == target) return target;
    else if (temp < target) {
        if (abs(temp - target) < del) {
            del = abs(temp - target);
            res = temp;
        }
        l++;
    }else {
        if (abs(temp - target) < del) {
            del = abs(temp - target);
            res = temp;
        }
        r--;
    }
}

题目解答

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if (nums.size() == 3) return nums[0] + nums[1] + nums[2];
        sort(nums.begin(), nums.end());
        
        int del = INT_MAX;
        int res;
        for (int i = 0; i < nums.size() - 2; i++) {
            int l = i + 1;
            int r = nums.size() - 1;
            while (l < r) {
                int temp = nums[i] + nums[l] + nums[r];
                if (temp == target) {
                    return target;
                }else if (temp < target) {
                    if (abs(temp - target) < del) {
                        del = abs(temp - target);
                        res = temp;
                    }
                    l++;
                }else if (temp > target) {
                    if (abs(temp - target) < del) {
                        del = abs(temp - target);
                        res = temp;
                    }
                    r--;
                }
            }
        }
        return res;
    }
};