leetcode——16.3 sum clsest题解

 题目要求：

给出一个整型数组，寻找其中的3个元素a,b,c使得a+b+c的值最接近另外一个给定的数字target

   代码：

	class Solution {
public:
    int threeSumClosest(vector& nums, int target) {
        int n = nums.size();
        if (n < 3) return 0; // 处理数组长度不足三个的情况
        sort(nums.begin(), nums.end());
        int closestSum = nums[0] + nums[1] + nums[2]; // 初始化为前三个数的和
        int minDiff = abs(closestSum - target); // 记录当前最小差值
        for(int i = 0; i < n - 2; i++){
            int left = i + 1;
            int right = n - 1;
            while(left < right){
                int sum = nums[left] + nums[right] + nums[i];
                int diff = abs(sum - target);
                if(diff < minDiff) { // 更新最小差值和最接近目标值的和
                    minDiff = diff;
                    closestSum = sum;
                }
                if(sum < target) left++; // 和小于目标值，左指针右移
                else right--; // 和大于目标值，右指针左移
            }
        }
        return closestSum;
    }
};

	
	
	

这道题使用了对撞指针（left和right）同时还使用了另外一个指针i用以遍历数组

其中索引i移动一次时，right和left要在满足right>left的条件下一直对向移动。

    right和left移动的条件：

            代码中已经写明。

值得一提的是：left和right的单次移动是有条件的，并不是在一个判断语句下（即并不是left++后right一定--）。有一个判断语句判断是应该left++还是right--。

    对撞指针的前提：

    数组一定是有序的！！！！。

       如果数组没有顺序，则不能使用对撞指针。这是因为指针移动后要进行比较和下一次移动如果数组是有序的，则right--后nums【rihgt】+nums【left】的值一定是减小的。left++后，nums【right】+nums【left】一定是增加的。

     最初的判断条件：

nums.size() >=3（这是理所当然的）不要忘记设置断言（assert）和判断（if）来避免这种情况。