@@ -0,0 +1,2209 @@
+package _3SumClosest;%0A%0A%0Aimport java.util.Arrays;%0A%0A/**%0A * Given an array S of n integers, find three integers in S such that the sum is closest to a given%0A * number, target. Return the sum of the three integers. You may assume that each input would have%0A * 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 */%0Apublic class Solution %7B%0A    public int threeSumClosest(int%5B%5D nums, int target) %7B%0A        // Sort the array first%0A        Arrays.sort(nums);%0A%0A        int n = nums.length;%0A        int closest = 0, offset = 0;%0A        boolean found = false;%0A%0A        for (int i = 0; i %3C n; i++) %7B%0A            if (i %3E 0 && nums%5Bi%5D == nums%5Bi - 1%5D) %7B%0A                // Avoid duplicated i%0A                continue;%0A            %7D%0A%0A            for (int j = i + 1; j %3C n; j++) %7B%0A                if (j %3E i + 1 && nums%5Bj%5D == nums%5Bj - 1%5D) %7B%0A                    // Avoid duplicated i%0A                    continue;%0A                %7D%0A                int v = nums%5Bi%5D + nums%5Bj%5D;%0A%0A                // Find all k if nums%5Bi%5D + nums%5Bj%5D + nums%5Bk%5D == 0%0A                int l = j + 1, r = n - 1, m = -1;%0A%0A                while (l %3C= r) %7B%0A                    m = (l + r) / 2;%0A                    int sum = v + nums%5Bm%5D;%0A                    if (sum == target) %7B%0A                        return sum;%0A                    %7D else if (sum %3E target) %7B%0A                        r = m - 1;%0A                    %7D else %7B%0A                        l = m + 1;%0A                    %7D%0A                %7D%0A%0A%0A                for (int k = r; k %3C= l; k++) %7B%0A                    if (k %3E j && k %3C n) %7B%0A                        if (!found) %7B%0A                            // The first valid number%0A                            closest = v + nums%5Bk%5D;%0A                            offset = Math.abs(target - closest);%0A                            found = true;%0A                        %7D else if (offset %3E Math.abs(target - v - nums%5Bk%5D)) %7B%0A                            closest = v + nums%5Bk%5D;%0A                            offset = Math.abs(target - closest);%0A                        %7D%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A        return closest;%0A    %7D%0A%7D

16. 3Sum Closest