@@ -0,0 +1,1943 @@
+package dtprogrammer.github.io.p15;%0A%0Aimport java.util.Arrays;%0Aimport java.util.LinkedList;%0Aimport java.util.List;%0A%0A/**%0A * 15. 3Sum%0A * %3Cp%3E%0A * Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique%0A * triplets in the array which gives the sum of zero.%0A * %3Cp%3E%0A * Note: The solution set must not contain duplicate triplets.%0A * %3Cp%3E%0A * For example, given array S = %5B-1, 0, 1, 2, -1, -4%5D,%0A * %3Cp%3E%0A * A solution set is:%0A * %5B%0A * %5B-1, 0, 1%5D,%0A * %5B-1, -1, 2%5D%0A * %5D%0A * %3Cp%3E%0A * Time complexity: O(n2)%0A * Space complexity: constant%0A */%0Apublic class Solution %7B%0A    public List%3CList%3CInteger%3E%3E threeSum(int%5B%5D nums) %7B%0A        List%3CList%3CInteger%3E%3E result = new LinkedList%3C%3E();%0A%0A        if (nums == null %7C%7C nums.length == 0) %7B%0A            return result;%0A        %7D%0A%0A        // sort the array%0A        Arrays.sort(nums);%0A%0A        for (int i = 0; i %3C nums.length - 2; i++) %7B%0A            // skip if this number is equal to the previous since we already process its triplet%0A            if (i == 0 %7C%7C nums%5Bi%5D != nums%5Bi - 1%5D) %7B%0A                int targetSum = 0 - nums%5Bi%5D;%0A                int low = i + 1;%0A                int high = nums.length - 1;%0A%0A                while (low %3C high) %7B%0A                    if (nums%5Blow%5D + nums%5Bhigh%5D == targetSum) %7B%0A                        result.add(Arrays.asList(nums%5Bi%5D, nums%5Blow%5D, nums%5Bhigh%5D));%0A                        // handle duplicates%0A                        while (low %3C high && nums%5Blow%5D == nums%5Blow + 1%5D) %7B%0A                            low++;%0A                        %7D%0A                        while (low %3C high && nums%5Bhigh%5D == nums%5Bhigh - 1%5D) %7B%0A                            high--;%0A                        %7D%0A                    %7D%0A                    if (nums%5Blow%5D + nums%5Bhigh%5D %3C targetSum) %7B%0A                        low++;%0A                    %7D else %7B%0A                        high--;%0A                    %7D%0A                %7D%0A            %7D%0A%0A        %7D%0A        return result;%0A    %7D%0A%7D%0A

15. 3Sum