@@ -0,0 +1,2275 @@
+/***%0A * Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.%0A *%0A * Note:%0A * Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a %E2%89%A4 b %E2%89%A4 c %E2%89%A4 d)%0A * The solution set must not contain duplicate quadruplets.%0A *     For example, given array S = %7B1 0 -1 0 -2 2%7D, and target = 0.%0A *%0A *     A solution set is:%0A *         (-1,  0, 0, 1)%0A *         (-2, -1, 1, 2)%0A *         (-2,  0, 0, 2)%0A */%0Aimport java.util.ArrayList;%0A%0Apublic class Solution %7B%0A    // Solution 1. Use the same strategy as 3 Sum. O(n%5E3) time exceeded%0A%0A    public ArrayList%3CArrayList%3CInteger%3E%3E fourSum(int%5B%5D num, int target) %7B%0A        ArrayList%3CArrayList%3CInteger%3E%3E ret = new ArrayList%3CArrayList%3CInteger%3E%3E();%0A        int n = num.length;%0A        if (n %3C 4) return ret;%0A        Arrays.sort(num);%0A        int i, j, k, p;%0A        int sum;%0A        for (i = 0; i %3C= n - 4; i++) %7B%0A            if (i %3E 0 && num%5Bi%5D == num%5Bi - 1%5D)  continue;%0A            for (j = i + 1; j %3C= n - 3; j++) %7B%0A                if (j %3E i + 1 && num%5Bj%5D == num%5Bj - 1%5D) continue;%0A                k = j + 1;%0A                p = n - 1;%0A                while ( k %3C p) %7B%0A                    sum = num%5Bi%5D + num%5Bj%5D + num%5Bk%5D + num%5Bp%5D;%0A                    if (sum %3E target) %7B%0A                        do %7B p--;%0A                        %7D while (k %3C p && num%5Bp%5D == num%5Bp + 1%5D);%0A                    %7D else if(sum %3C target) %7B%0A                        do %7B k++;%0A                        %7D while (k %3C p && num%5Bk%5D == num%5Bk - 1%5D);%0A                    %7D else %7B%0A                        ArrayList%3CInteger%3E soluset = new ArrayList%3CInteger%3E();%0A                        soluset.add(num%5Bi%5D);%0A                        soluset.add(num%5Bj%5D);%0A                        soluset.add(num%5Bk%5D);%0A                        soluset.add(num%5Bp%5D);%0A                        ret.add(soluset);%0A                        p--;%0A                        do %7B k++;%0A                        %7D while (k %3C p && num%5Bk%5D == num%5Bk - 1%5D);%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A        return ret;%0A    %7D%0A    // Solution 2. T; Mean O(n%5E2), Worst O(n%5E4), S: O(n%5E2)%0A    // Using hashmap to store sum of two numbers%0A%0A    // Solution 3. T: O(n%5E2) S: O(n%5E2)%0A%0A%7D%0A

add 4Sum.java