The sum of the nearest three numbers

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.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/3s… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution one: double pointer method

First, sort the array and get an initial result, difference. Then, the first number is traversed from the first number, the second number second and the third number are traversed from both sides of the subsequent array to the middle, respectively. If the traversal is closer to target than difference, Update difference until traversal is complete and return result corresponding to difference.

Solution and LeetCode-015- sum of three numbers this problem solution is similar, can be compared for reference.

import java.util.Arrays;

public class Solution {
    /** * double pointer *@param nums
     * @param target
     * @return* /
    public static int threeSumClosest(int[] nums, int target) {
        if (nums.length == 3) {
            return nums[0] + nums[1] + nums[2];
        }
        Arrays.sort(nums);

        int result = nums[0] + nums[1] + nums[2];
        int difference = Math.abs(result - target);
        // The first number
        for (int first = 0; first < nums.length - 2; first++) {
            // Filter out duplicates
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            for (int second = first + 1; second < nums.length - 1; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    // Filter out duplicates
                    continue;
                }

                int third = nums.length - 1;
                while (second < third) {
                    Update result when the sum of the three numbers is closer than the current result
                    if(Math.abs(nums[first] + nums[second] + nums[third] - target) < difference) { result = nums[first] + nums[second] + nums[third]; difference = Math.abs(result - target); } third--; }}}return result;
    }

    public static void main(String[] args) {
        int[] nums = new int[] {0.1.2.3.4.5.6};
        System.out.println(threeSumClosest(nums, 2)); }}Copy the code

Healthy oneself is the greatest care for others.