Drawing solution algorithm: 16. The sum of the closest three numbers

Topic link

Leetcode-cn.com/problems/3s…

Topic describes

Given an array of n integers nums and a target value target. Identify the three integers in NUMs so that their sum is closest to target. Returns the sum of these three numbers. Assume that there is only one answer for each set of inputs.

For example, given the array nums = [-1, 2, 1, -4], and target = 1. The sum of the three numbers closest to target is 2. (-1 + 2 + 1 = 2).Copy the code

The problem solving scheme

Train of thought

Tags: Sort and double pointer
In this problem, because we need to calculate three numbers, if we rely on violence enumeration, the time complexity will reach O(n^3), so we need to reduce the time complexity
Let’s do array sort, order nlogn.
In the array nums, iterate over one value at a time using its subscript I to form a fixed nums[I]
Reuse the pre-pointer pointstart = i + 1, the back pointer points toend = nums.length - 1At the end, at the end
According to thesum = nums[i] + nums[start] + nums[end], judge the distance between sum and target, and update the result ANS if it is closer
Sum = target; if sum = targetsum > target 则 end--If thesum < target 则 start++If thesum == targetIf the distance is 0, the result is returned
The entire traversal process, fixed value n times, double pointer n times, time complexity O(n^2)
Total time complexity: O(nlogn) + O(n^2) = O(n^2)

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
                    returnans; }}returnans; }}Copy the code