@@ -0,0 +1,2012 @@
+import java.util.Arrays;%0A%0A//16. 3Sum Closest%0A/**%0A* 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.%0A* %0A*     For example, given array S = %7B-1 2 1 -4%7D, and target = 1.%0A* %0A*     The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).%0A* %0A* Tags: Array, Two Pointers%0A* %0A* Similar Problems: (M) 3Sum, (M) 3Sum Smaller%0A* %0A* Author: Xinyue Zhang%0A*/%0A%0Apublic class Solution %7B%0A    public int threeSumClosest(int%5B%5D nums, int target) %7B%0A        Arrays.sort(nums);%0A        int n = nums.length;%0A        if (n %3C 3) return 0;%0A        %0A        //if maximum smaller than target, then return%0A        int res = nums%5Bn - 1%5D + nums%5Bn - 2%5D + nums%5Bn - 3%5D;%0A        if (res %3C target) return res;%0A        %0A        //if maximum larger than target, then return%0A        res = nums%5B0%5D + nums%5B1%5D + nums%5B2%5D;%0A        if (res %3E target) return res;%0A        %0A        for (int i = 0; i %3C n - 2; i++) %7B%0A%0A            if (i %3E 0 && nums%5Bi%5D == nums%5Bi - 1%5D) continue;%0A            //two pointers%0A            int j = i + 1, k = n - 1;%0A            %0A            while (j %3C k) %7B%0A                int sum = nums%5Bi%5D + nums%5Bj%5D + nums%5Bk%5D;%0A                if(Math.abs(sum - target) %3C Math.abs(res - target))%0A                    res = sum;%0A                %0A                if (sum %3E target) %7B%0A                    k--;%0A                    while (j %3C k && nums%5Bk%5D == nums%5Bk + 1%5D) k--;%0A                %7D%0A                else if (sum %3C target) %7B%0A                    j++;%0A                    while (j %3C k && nums%5Bj%5D == nums%5Bj - 1%5D) j++;%0A                %7D%0A                else%0A                    return sum;%0A            %7D%0A        %7D%0A        return res;%0A    %7D%0A%0A    %0A    public static void main(String%5B%5D args) %7B%0A        int%5B%5D nums = %7B0, 2, 1, -3%7D;%0A        int target = 1;%0A        Solution sol = new Solution();%0A        int res = sol.threeSumClosest(nums, target);%0A        System.out.println(res);%0A    %7D%0A%7D%0A

Create 016_3Sum_Closest.java