LeetCode - 3Sum

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: 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]
]

题解

题意很清晰，给一个数组，找出所有的和为0的三元组。（答案不允许有重复的三元组）

解题过程

第一版(stupid)

思路：拿到题的一瞬间，觉得很简单，把所有的都比较一次，然后对答案做排序及hash，重复的抛弃掉就行了

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        List<String> hash = new ArrayList<String>();
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> tmp = new ArrayList<Integer>(3);
                        tmp.add(nums[i]);
                        tmp.add(nums[j]);
                        tmp.add(nums[k]);
                        tmp = this.sort(tmp);
                        String key = tmp.get(0) + "" + tmp.get(1) + "" + tmp.get(2);
                        if (this.contains(hash, key)) {
                            continue;
                        }

                        hash.add(key);
                        result.add(tmp);
                    }
                }
            }
        }



        return result;
    }

    private boolean contains(List<String> hash, String key) {
        for (String hash_key : hash) {
            if (key.equals(hash_key)) {
                return true;
            }
        }
        return false;
    }

    private List<Integer> sort(List<Integer> target) {
        for (int i = 0; i < target.size(); i++) {
            for (int j = i + 1; j < target.size(); j++) {
                if (target.get(i) > target.get(j)) {
                    int tmp = target.get(i);
                    target.set(i, target.get(j));
                    target.set(j, tmp);
                }
            }
        }
        return target;
    }
}

拿到LeetCode上一提交，我的天，最后几个测试用例跑了超久，最终Time Limit Exceeded
分析了一下，发现使用的算法太笨重了，与其说算法，不如说写了堆垃圾，遂重新分析了一下解题算法

第二版(better)

思路：第一版的算法复杂度达到了O(n^3)，导致在测试用例大一些的时候，会超时；分析发现，我们可以先将整个数组进行排序，然后将最大最小值和他们区间内的数值进行比较，若等于0，则将结果记录起来，若小于0，则说明最大值过大，若大于0，则说明中间数值过小，通过这种方式，不断的缩小数值区间，最后可以得到结果，整体算法复杂度降低到了O(n^2)
O(n^2) => 中间数值缩小n次 * 最小值增大n次

    List<List<Integer>> result = new ArrayList<List<Integer>>();

    nums = this.sort(nums);
    int i = 0;

    // 迭代法
    while (i < nums.length - 2) {// 比较区间为[i, nums.length - 1]
        int j = i + 1; // 中间数
        int k = nums.length - 1; // 最右数

        while (j < k) { // 内循环终止条件
            int sum = nums[i] + nums[j] + nums[k];
            if (sum == 0) {
                List<Integer> tmp = new ArrayList<Integer>();
                tmp.add(nums[i]);
                tmp.add(nums[j]);
                tmp.add(nums[k]);
                result.add(tmp);
            }

            // 小于等于0 时 中间数偏小 向右移动
            if (sum <= 0) {
                while (nums[j] == nums[++j] && j < k) {
                    // 若下一个数和当前数相同 则继续右移
                }
            }

            // 大于等于0时 末尾数偏大 向左移动
            if (sum >= 0) {
                while (nums[k--] == nums[k] && j < k) {
                    // 若前一个数和当前数相同 继续左移
                }
            }
        }

        while (nums[i] == nums[++i] && i < j) {
            // 最左数向右移动 进行下一轮比较
        }
    }

    return result;
}

private int[] sort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] > nums[j]) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
    }
    return nums;
}

经过验证，所有的测试用例都跑过了，看来以后遇到问题还是要多思考的^_^