[leetcode16] the sum of the nearest three numbers (double pointer)

One 、 subject

Two 、 Ideas

and leetcode15 The sum of three is similar , Three level cycle time complexity $O(n^3)$ Too high , Use double pointer, although it can't drop to $O(n)$, But it is the common routine of this kind of questions ：

• Go through the array elements , The current element is num[i];
• Set the left and right pointers , The right pointer is the right endpoint , Note that the left pointer is left + 1, Not from 0 Start , Otherwise, there will be repeated elements due to repeated traversal ; When the sum of three numbers is greater than target be right Move left to reduce the value .
• Every time we judge the current combination of three numbers , That is, calculate and target Difference between , If it is lower than the current minimum difference minAbsError Still small , You can update .

3、 ... and 、 Code

class Solution {
    
public:
    int threeSumClosest(vector<int>& nums, int target) {
    
        sort(nums.begin(), nums.end());
        int ans = 0, left = 0, right = 0; 
        int minAbsError = INT_MAX, error = 0, absError = 0, temp = 0;
        for(int i = 0; i < nums.size() - 2; i++){
    
            left = i + 1;
            right = nums.size() - 1;    
            while(left < right){
    
                temp = nums[i] + nums[left] + nums[right];
                error = temp - target;
                absError = abs(error);
                if(minAbsError > absError){
    
                    // The update process 
                    ans = temp;
                    minAbsError = absError;
                }else if(error > 0){
    
                    right--;
                }else{
    
                    left++;
                }
            }    
        }
        return ans;
    }
};