Question

Formatted question description: https://leetcode.ca/all/16.html

16	3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target.
Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

@tag-array

Algorithm

This question allows us to find the sum of the three numbers closest to the given value. It is a little more difficult on the basis of the previous 3Sum.

Then this question requires to return the value that is closest to the given value. Ensure that the absolute value of the difference between the current three numbers and the given value is the smallest, so you need to define a variable diff to record the absolute value of the difference, and then you still have to sort the array first, and then start traversing the array, the idea follows that The sum of the three numbers is very similar.

  • First determine one number, and then use the two pointers left and right to slide to find the other two numbers.
  • For every two numbers determined, find the sum of the three numbers, and then calculate and give the absolute value of the value difference is stored in newDiff,
  • and then compared with diff and updated diff and the result closest, the code is as follows:

Code

Java

public class Three_Sum_Closest {

	public static void main(String[] args) {

        Three_Sum_Closest out = new Three_Sum_Closest();
        Solution s = out.new Solution();

        System.out.println(s.threeSumClosest(new int[]{-1, 2, 1, -4}, 1));
	}

    // time: O(N)
    // space: O(1)
    public class Solution {
        public int threeSumClosest(int[] nums, int target) {
            if (nums.length < 3) {
                return Integer.MIN_VALUE;
            }

            Arrays.sort(nums);

            int closest = Integer.MAX_VALUE;
            int result = Integer.MAX_VALUE;

            // hold one pointer, other two pointer moving
            for (int ancher = 0; ancher < nums.length; ancher++) {

                if (ancher > 0 && nums[ancher] == nums[ancher - 1]) continue;

                int i = ancher + 1;
                int j = nums.length - 1;

                while (i < j) {

                    int sum = nums[ancher] + nums[i] + nums[j];
                    if (sum == target) {
                        return target;

                    } else if (sum < target) {
                        // check if closest
                        if (closest > Math.abs(sum - target)) {
                            closest = Math.abs(sum - target);
                            result = sum;
                        }

                        i++;

                        // @note: same here, possibly updated already, note i-1 or i+1
                        while (i < j && nums[i] == nums[i - 1]) {
                            i++;
                        }

                    } else {
                        // check if closest
                        if (closest > Math.abs(sum - target)) {
                            closest = Math.abs(sum - target);
                            result = sum;
                        }

                        j--;

                        // @note: same here, possibly updated already, note i-1 or i+1
                        while (j > i && j + 1 < nums.length && nums[j] == nums[j + 1]) {
                            j--;
                        }

                    }
                }
            }

            return result;
        }
    }
}

All Problems

All Solutions