3Sum Closest

Leetcode

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).

Analysis

排序+固定一个指针（循环该指针位置）+另外两个指针从两端靠拢找最接近值(2sum 问题)

1. Use 3 pointers:
   1. Current element
   2. Next element
   3. Last element
2. Loop over current element, keep update the closest sum
3. If sum < target, next move to next
4. If sum > target, last move to second last
5. If sum = target, return

Code

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int result = nums[0]+nums[1]+nums[nums.length-1];
        Arrays.sort(nums);
        for(int i=0; i<nums.length-2;i++){
            int str =i+1;
            int end =nums.length-1;
            while(str<end){
                int sum = nums[i]+nums[str]+nums[end];
                if (sum==target) {return sum;}
                else if(sum < target) {str++;}
                else {end--;}
                if (Math.abs(sum-target) < Math.abs(result-target)) {result = sum;}
            }
        }
        return result;
    }
}

Reference

1. Leetcode