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.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},    A solution set is:    (-1, 0, 1)    (-1, -1, 2)

https://oj.leetcode.com/problems/3sum/

思路1：先排序（用于结果展示和去重），对于每个元素target（注意去重），找另外两个元素使得和为-target，就转化成了n次求2Sum。复杂度O(n^2)。

NSum扩展：可参考 这里

import java.util.ArrayList;import java.util.Arrays;public class Solution {    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();        if (num == null || num.length < 3)            return result;        int n = num.length;        Arrays.sort(num);        for (int i = 0; i < n; i++) {            int target = -num[i];            int p = i + 1, q = n - 1;            while (p < q) {                if (num[p] + num[q] < target)                    p++;                else if (num[p] + num[q] > target)                    q--;                else {                    ArrayList<Integer> tmp = new ArrayList<Integer>();                    tmp.add(-target);                    tmp.add(num[p]);                    tmp.add(num[q]);                    result.add(tmp);                    p++;                    q--;                    // remove duplicates                    while (p < n && num[p] == num[p - 1])                        p++;                    while (q >= i + 1 && num[q] == num[q + 1])                        q--;                }            }            // remove duplicates            while (i < n - 1 && num[i + 1] == num[i])                i++;        }        return result;    }    public static void main(String[] args) {        System.out.println(new Solution().threeSum(new int[] { 0 }));        System.out.println(new Solution().threeSum(new int[] { -1, 0 }));        System.out.println(new Solution().threeSum(new int[] { 0, 1, -1, }));        System.out.println(new Solution().threeSum(new int[] { 0, 1, 1, }));        System.out.println(new Solution().threeSum(new int[] { -1, 0, 1, 2, -1, -4 }));        System.out.println(new Solution().threeSum(new int[] { 0, 0, 0, 0, 1, -1 }));        System.out.println(new Solution().threeSum(new int[] { -7, -1, -13, 2, 13, 2, 12, 3, -11, 3, 7, -15, 2, -9,                -13, -13, 11, -10, 5, -13, 2, -12, 0, -8, 8, -1, 4, 10, -13, -5, -6, -4, 9, -12, 5, 8, 5, 3, -4, 9, 13,                10, 10, -8, -14, 4, -6, 5, 10, -15, -1, -3, 10, -15, -4, 3, -1, -15, -10, -6, -13, -9, 5, 11, -6, -13,                -4, 14, -3, 8, 1, -4, -5, -12, 3, -11, 7, 13, 9, 2, 13, -7, 6, 0, -15, -13, -11, -8, 9, -14, 1, 11, -7,                13, 0, -6, -15, 11, -6, -2, 4, 2, 9, -15, 5, -11, -11, -11, -13, 5, 7, 7, 5, -10, -7, 6, -7, -11, 13,                9, -10, -9 }));        System.out.println(new Solution().threeSum(new int[] { -2, 0, 1, 1, 2 }));        System.out.println(new Solution().threeSum(new int[] { -4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6 }));    }}

参考：

http://tech-wonderland.net/blog/summary-of-ksum-problems.html

http://www.cnblogs.com/TenosDoIt/p/3649607.html