@@ -0,0 +1,1768 @@
+package _3Sum;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.List;%0A%0A/**%0A * Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all%0A * unique triplets in the array which gives the sum of zero.%0A */%0Apublic class Solution %7B%0A    public List%3CList%3CInteger%3E%3E threeSum(int%5B%5D nums) %7B%0A        // Sort the array first%0A        Arrays.sort(nums);%0A%0A        int n = nums.length;%0A%0A        List%3CList%3CInteger%3E%3E resultSet = new ArrayList%3C%3E();%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 == 0) %7B%0A                        break;%0A                    %7D else if (sum %3E 0) %7B%0A                        r = m - 1;%0A                    %7D else %7B%0A                        l = m + 1;%0A                    %7D%0A                %7D%0A                if (m %3E j && m %3C n && v + nums%5Bm%5D == 0) %7B%0A                    // A valid m found%0A                    List%3CInteger%3E rv = new ArrayList%3C%3E();%0A                    rv.add(nums%5Bi%5D);%0A                    rv.add(nums%5Bj%5D);%0A                    rv.add(nums%5Bm%5D);%0A                    resultSet.add(rv);%0A                %7D%0A            %7D%0A        %7D%0A        return resultSet;%0A    %7D%0A%7D

15. 3Sum