Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

You are given an array of integers of length n nums and a target value target. Select three integers from nums whose sum is closest to target.

Returns the sum of these three numbers.

Assume that exactly one solution exists for each set of inputs.

The sample

The sample1: Enter nums = [-1.2.1, -4], target = 1Output:2Explanation: The sum closest to target is2 (-1 + 2 + 1 = 2). The sample2: Input: nums = [0.0.0], target = 1Output:0
Copy the code

Ii. Solution:

Method one – three cyclic comparison method

  • Principle. Based on the sum of all three records, the smallest value is obtained
  • Train of thought. First record the sum of all three records, and then loop to determine the smallest value

Code:

var threeSumClosest = function(nums, target) {
    let arr = []
    for(let i =0; i<nums.length; i++){for(let j = i+1; j<nums.length; j++){for(let k = j+1; k<nums.length; k++){console.log(nums[i], nums[j], nums[k])
                arr.push(nums[i]+nums[j]+nums[k])
            }
        }
    }
    let min = Math.abs(target-arr[0])
    let minNum = arr[0]
    for(let i = 1; i<arr.length; i++){let item = arr[i]
        let diffNum = Math.abs(target-item)
        if(diffNum < min){
            minNum = item
            min = diffNum
        }
    }
    return minNum
};

Copy the code

I ran out of time, so I had to optimize

  • Optimize your thinking. As you loop, you can determine the minimum.

Code:

var threeSumClosest = function(nums, target) {
    let sum = 0
    let min = nums[0]+nums[1]+nums[2]
    for(let i =0; i<nums.length-2; i++){for(let j = i+1; j<nums.length-1; j++){for(let k = j+1; k<nums.length; k++){ sum = (nums[i] + nums[j] + nums[k]);if(Math.abs(target-sum) < Math.abs(target-min)){
                    min = sum
                }
            }
        }
    }
    
    return min
};
Copy the code

Method two double pointer traversal method

  • Principle. The input array is sorted first, and then evaluated using a double pointer. So here we have to move the pointer after we determine the size.

Code:

const threeSumClosest = (nums, target) = > {
    nums.sort((a, b) = > a - b);
    let min = Infinity;
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        let [left, right] = [i + 1, len - 1];
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (Math.abs(sum - target) < Math.abs(min - target)) {
                min = sum;
            }
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                returnsum; }}}return min;
};
Copy the code

Scheme comparison

Solution 1 Time complexity O(N3) Solution 2 Time complexity O(n2)

Third, summary

  • This problem can be three cycle comparison method and two pointer traversal method
  • Triple cycle comparison method is mainly based on the sum of all the records of three numbers, get the minimum value
  • The double-pointer traversal method sorts the input array first, and calculates the value of the double-pointer after sorting. So here we have to move the pointer after we determine the size.

If there are any errors in this article, please correct them in the comments section