• 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: The solution set must not contain duplicate triplets.
  從給定的數(shù)組中找到所有和為0的3元組。并且兩兩三元組中的數(shù)字不可相同。

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

一、暴力破解：

• 技巧：既然要得到所有可能的三元組，三重for循環(huán)即可，注意如何寫(xiě)三重for循環(huán)。

        for (int i = 0; i < len; ++i)
            for (int j = i + 1; j < len; ++j)
                for (int k = j + 1; k < len; ++k)

• 代碼如下，LeetCode理所當(dāng)然的超時(shí)了：

    public static List<List<Integer>> fourSum(int[] nums, int target) 
    {
        int len = nums.length;
        if (nums == null || nums.length < 3 )
            return new ArrayList<List<Integer>>();

        List<Integer> ns = null;
        HashSet<List<Integer>> set = new HashSet<>();

        //進(jìn)行暴力搜索，嘗試所有的三人組
        for (int i = 0; i < len; ++i)
        {
            for (int j = i + 1; j < len; ++j)
            {
                for (int k = j + 1; k < len; ++k)
                {
                    //filter the sum not equal target
                    if (nums[i] + nums[j] + nums[k] != target)
                    {
                        continue;
                    }

                    ns = new ArrayList<>();
                    ns.add(nums[i]);
                    ns.add(nums[j]);
                    ns.add(nums[k]);
                    //對(duì)三人組進(jìn)行排序，方便利用HashSet去重
                    Collections.sort(ns);
                    //去重
                    set.add(ns);
                }
            }
        }

        List<List<Integer>> lists = new ArrayList<>();
        for (List<Integer> s : set)
            lists.add(s);

        return lists;
    }

二、排序，固定一個(gè)指針，轉(zhuǎn)化為2Sum問(wèn)題

• 第一步，對(duì)數(shù)組排序。
• 第二步：
  分析1：對(duì)于元素 S[i] ， 最后的答案可以分為兩種，包含 S[i] 的，和不包含 S[i] 的。當(dāng)包含 S[i] 的情況都找到后，后續(xù)就可以不用在考慮 S[i] 。對(duì)于 S[i] ， l = i+1, r = len-1 。若 s[i] + S[l] + S[r] == 0， 則為原問(wèn)題的一個(gè)解。

當(dāng) S[i] + S[l] > -S[r] 時(shí)，則 r--
當(dāng) S[i] + S[l] < -S[r] 時(shí)，則 l++
當(dāng) S[i] + S[i] = -S[r] 時(shí)， 表示是原問(wèn)題的一個(gè)解，則 l++, r--;

• 第三步，性能優(yōu)化。同樣根據(jù)分析1，若 S[i] == S[i+1]，可以跳過(guò)。

    public static List<List<Integer>> threeSumBySort(int[] nums) {
        int len = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        if (nums == null || nums.length < 3 )
            return lists;

        //sort
        Arrays.sort(nums);
        int low = 0;
        int high = 0;

        //1,2,3,4(固定指針從index = 2 開(kāi)始)
        for (int i = 0; i < len - 2; ++i)
        {
            //如果最小的數(shù)都大于0，break
            if (nums[i] > 0)
                break;

            //優(yōu)化，去重
            if (i > 0)
            {
                if (nums[i] == nums[i -1])
                    continue;
            }
            low = i + 1;
            high = len - 1;
            while (low < high)
            {
                //優(yōu)化，去重
                if (low > i + 1)
                {
                    if (nums[low] == nums[low - 1])
                    {
                        ++low;
                        continue;
                    }
                }
                //優(yōu)化，去重
                if (high < len - 1)
                {
                    if (nums[high] == nums[high + 1])
                    {
                        --high;
                        continue;
                    }
                }

                if (nums[i] + nums[low] + nums[high] == 0)
                {
                    lists.add(Arrays.asList(nums[i], nums[low], nums[high]));
                    ++low;
                    --high;
                }else if (nums[i] + nums[low] + nums[high] < 0) {
                    //如果小于0，則low index右移
                    ++low;
                }else {
                    //如果大于0，則high index左移
                    --high;
                }
            }
        }
        return lists;
    }

https://github.com/yuanoOo/Algorithm/tree/master/LeetCode