3Sum——LeetCode

• 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.
  从给定的数组中找到所有和为0的3元组。并且两两三元组中的数字不可相同。

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

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

一、暴力破解：

• 技巧：既然要得到所有可能的三元组，三重for循环即可，注意如何写三重for循环。

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

• 代码如下，LeetCode理所当然的超时了：

    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<>();

        //进行暴力搜索，尝试所有的三人组
        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]);
                    //对三人组进行排序，方便利用HashSet去重
                    Collections.sort(ns);
                    //去重
                    set.add(ns);
                }
            }
        }

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

        return lists;
    }

二、排序，固定一个指针，转化为2Sum问题

• 第一步，对数组排序。
• 第二步：
  分析1：对于元素 S[i] ， 最后的答案可以分为两种，包含 S[i] 的，和不包含 S[i] 的。当包含 S[i] 的情况都找到后，后续就可以不用在考虑 S[i] 。对于 S[i] ， l = i+1, r = len-1 。若 s[i] + S[l] + S[r] == 0， 则为原问题的一个解。

当 S[i] + S[l] > -S[r] 时，则 r--
当 S[i] + S[l] < -S[r] 时，则 l++
当 S[i] + S[i] = -S[r] 时， 表示是原问题的一个解，则 l++, r--;

• 第三步，性能优化。同样根据分析1，若 S[i] == S[i+1]，可以跳过。

    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 开始)
        for (int i = 0; i < len - 2; ++i)
        {
            //如果最小的数都大于0，break
            if (nums[i] > 0)
                break;

            //优化，去重
            if (i > 0)
            {
                if (nums[i] == nums[i -1])
                    continue;
            }
            low = i + 1;
            high = len - 1;
            while (low < high)
            {
                //优化，去重
                if (low > i + 1)
                {
                    if (nums[low] == nums[low - 1])
                    {
                        ++low;
                        continue;
                    }
                }
                //优化，去重
                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