最接近的两数之和

题目描述

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

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

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

解法一

暴力破解，需要O(N^2)的时间复杂度，能不能降低？我们知道在乱序情况下，只能做到两个循环去遍历，如果排序，则可能可以利用头尾指针去智能化地遍历（和大于target则右指针左移，小于target则左指针右移），这样只需要O(N)的复杂度，加上排序复杂度O(NlogN)，最后复杂度是O(NlogN)
头尾双指针算法的正确性如何证明？我们要找最接近的两数之和，如此移动，如果能证明不会错失最优解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    // 返回最接近的两数之和
    int twoSumClosest(vector<int> nums, int target) {
        int n = nums.size();
        if(n <= 1) return 0;
        sort(nums.begin(), nums.end());
        int left = 0;
        int right = n - 1;
        int min_diff = INT_MAX;
        int closest_sum;
        while(left < right) {
            int sum = nums[left] + nums[right];
            int diff = abs(sum - target);
            if(diff < min_diff) {
                min_diff = diff;
                closest_sum = sum;
            }
            // 移动指针
            if(sum > target) {
                --right;
            } else {
                ++left;
            }
        } // end while
        return closest_sum;
    }
};