This is the 13th day of my participation in Gwen Challenge

preface

The sum of the nearest three numbers in question 16 is as follows:

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.

Example:

Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The closest sum to target is 2 (-1 + 2 + 1 = 2).

A, thinking

This problem and the front of the fifteenth problem – the sum of three numbers on the idea is the same, or the use of sorting + double pointer to achieve.

The idea is roughly divided into the following two steps

  • Sort the NUMs in ascending order
  • Select the first two elements from the left and the third element from the right, saving the closest value

Here is an example to describe the specific steps:

Assume that nums = [-1,2,1,-4], target = 1, and ret is returned

  1. Order nums in ascending order, i.enums = [-4, -1, 1, 2]
  2. In order to4 and 1As the first two elements, the third element is selected from right to left. The result is obtained through this cycle(-4) + (-1) + 2 = (-3), that is ret = -3
  3. In order to4 and 1As the first two elements, the third element is only 2. After this loop, the result is updated to(-4) + 1 + 2 = (-3), that is ret = -1
  4. In order to1 and 1As the first two elements, the third element is only 2. After this loop, the result is updated to(-1) + 1 + 2 = 2, that is ret = 2
  5. Returns the result 2 nearest target=1

Second, the implementation

The implementation code

To make it easier to find the closest values, I initially set the result to the first three elements of the NUMS array.

    public int threeSumClosest(int[] nums, int target) {
        int ret = nums[0] + nums[1] + nums[2];
        // Change the array to ascending order first
        Arrays.sort(nums);
        // Use double pointer traversal
        for (int i=0; i<nums.length-2; i++) {
            if(i ! =0 && nums[i] == nums[i-1])
                continue;
            int m = nums.length-1;
            for (int j=i+1; j<nums.length-1; j++) {
                if(j ! = i+1 && nums[j] == nums[j-1])
                    continue;
                // Move the pointer to the left with the right pointer to the right of the left pointer
                while(j < m && nums[i]+nums[j]+nums[m]>target) {
                    // take the nearest value
                    if (Math.abs(ret - target) >= Math.abs(nums[i]+nums[j]+nums[m] - target)) {
                        ret = nums[i]+nums[j]+nums[m];
                    }
                    m = m-1;
                }
                if (j == m) {
                    break;
                }
                // take the nearest value
                if (Math.abs(ret - target) >= Math.abs(nums[i]+nums[j]+nums[m] - target)) {
                    ret = nums[i]+nums[j]+nums[m];
                }
                if (ret == target) {
                    returnret; }}}return ret;
    }
Copy the code

test

    public static void main(String[] args) {
        int ret = new Number16().threeSumClosest(new int[] {1.2.5.10.11}, 12);
        System.out.println(ret);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥