[leetcode] 3Sum

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