@@ -0,0 +1,1933 @@
+/***%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 triplets in the array which gives the sum of zero.%0A *%0A * Note:%0A * Elements in a triplet (a,b,c) must be in non-descending order. (ie, a %E2%89%A4 b %E2%89%A4 c)%0A * The solution set must not contain duplicate triplets.%0A *     For example, given array S = %7B-1 0 1 2 -1 -4%7D,%0A *%0A *         A solution set is:%0A *             (-1, 0, 1)%0A *             (-1, -1, 2)%0A */%0Aimport java.util.ArrayList;%0A%0Apublic class Solution %7B%0A    // Solution 1. O(n%5E2) O(1)%0A    // Sort first,%0A    // Fixed i, %0A    // j starts at i + 1, k starts at n - 1,%0A    // increase j, decrease k until num%5Bi%5D + num%5Bj%5D + num%5Bk%5D == 0;%0A    // be careful with duplicated values.%0A%0A    public ArrayList%3CArrayList%3CInteger%3E%3E threeSum(int%5B%5D num) %7B%0A        int n = num.length;%0A        ArrayList%3CArrayList%3CInteger%3E%3E ret = new ArrayList%3CArrayList%3CInteger%3E%3E();%0A        if (n %3C 3) return ret;%0A        Arrays.sort(num);%0A        int target = 0;%0A        int i, j, k;%0A        for(i = 0; i %3C n - 2; i++) %7B%0A            j = i + 1;%0A            if (i %3E 0 && num%5Bi%5D == num%5Bi - 1%5D)%0A                continue;%0A            k = n - 1;%0A            while (j %3C k) %7B%0A                if (num%5Bi%5D + num%5Bj%5D + num%5Bk%5D %3C target) %7B%0A                    ++j;%0A                    while (num%5Bj%5D == num%5Bj - 1%5D && j %3C k) j++;%0A                %7D else if (num%5Bi%5D + num%5Bj%5D + num%5Bk%5D %3E target) %7B%0A                    --k;%0A                    while (num%5Bk%5D == num%5Bk + 1%5D && j %3C k) k--;%0A                %7D else %7B%0A                    ArrayList%3CInteger%3E triplet = new ArrayList%3CInteger%3E();%0A                    triplet.add(num%5Bi%5D);%0A                    triplet.add(num%5Bj%5D);%0A                    triplet.add(num%5Bk%5D);%0A                    ret.add(triplet);%0A                    ++j;%0A                    --k;%0A                    while (num%5Bj%5D == num%5Bj - 1%5D && j %3C k) j++;%0A                %7D%0A            %7D%0A        %7D%0A        return ret;%0A    %7D%0A%7D%0A

add 3Sum.java