[leetcode] 16. The sum of the nearest three numbers

16、 The closest sum of three

subject ：

Give you a length of n Array of integers for nums and A target value target. Please start from nums Choose three integers , Make their sum with target Nearest .

Returns the sum of the three numbers .

It is assumed that there is only exactly one solution for each set of inputs .

Example 1：

 Input ：nums = [-1,2,1,-4], target = 1
 Output ：2
 explain ： And  target  The closest and  2 (-1 + 2 + 1 = 2) .

Example 2：

 Input ：nums = [0,0,0], target = 1
 Output ：0

Tips ：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10 ^4 <= target <= 10 ^4

Their thinking ：

This topic and 15、 Sum of three numbers , Very similar , You can use the idea of double pointers in the same way .

First , The title is the closest target Value , Closest, that is, the absolute value of the sum of three numbers is closest to the target value .

We can consider using... Directly Triple loop enumerating triples , Find the one closest to the target value as the answer , The time complexity is O(N^3). However, this question is N The maximum is 1000, Will exceed the time limit . So it's not advisable to .

therefore , The right thinking is ： Sort + Double pointer

1. label ： Sort and double pointer
2. Because there are three numbers to calculate , If we count by violence, the time complexity will be O(n^3), Need to reduce time complexity
3. First, sort the array , Time complexity O(nlogn)
4. In the array nums in , Traversal , Each traversal of a value uses its subscript i, Form a fixed value nums[i]
5. Before using again, the pointer points to start = i + 1 It's about , The back pointer points to end = nums.length - 1 It's about , It's the end
6. according to sum = nums[i] + nums[start] + nums[end] Result , Judge sum And target target Distance of , Update results if closer ans
7. At the same time judge sum And target The size of the relationship , Because the array is ordered , If sum > target be end–, If sum <
   target be start++, If sum == target The distance is 0 Direct return
8. The whole traversal process , The fixed value is n Time , The double pointer is n Time , The time complexity is O(n^2)
9. Total time complexity ：O(nlogn) + O(n^ 2) = O( n^2)

Reference code ：

class Solution {
    
    public int threeSumClosest(int[] nums, int target) {
    
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length;i++) {
    
            int start = i+1, end = nums.length - 1;
            while(start < end) {
    
                int sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if(sum > target)
                    end--;
                else if(sum < target)
                    start++;
                else
                    return ans;
            }
        }
        return ans;
    }
}