LeetCode 16. 排列序列

思路

1. 排序数组：对数组进行从小到大排序。

2. 遍历固定一个元素：遍历数组中的每个元素作为三个数中的第一个数，固定该元素后，使用双指针在剩余的子数组中寻找另外两个数。

3. 双指针逼近target：对于每个固定的元素，使用左右指针分别指向剩余子数组的开始和结尾。计算当前三个数的和，如果该和更接近目标值，则更新最接近的和。如果发现当前三数和等于target，则直接返回；如果三数和<target，说明需要更大的数，左指针右移；如果三数和>target，说明需要更小的数，右指针左移。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int zx=nums[0]+nums[1]+nums[2]; //初始化为前3个值

        // i从0到n-3
        for(int i=0;i<n-2;i++) {
            int zz=i+1; // 第二个数的位置
            int yy=n-1; // 第三格数的位置
            while(zz<yy) { // 不能两次取同一位置上的数，故不能=
                int cur=nums[i]+nums[zz]+nums[yy];
                if(abs(cur-target)<abs(zx-target)) { //发现里target更近了
                    zx=cur;
                }
                if(cur==target) { 
                    return cur;
                } else if(cur<target) {
                    ++zz; //数太小，左指针右移
                } else {
                    --yy; //数大了，右指针左移
                }
            }
        }
        return zx;
    }
};