Three Sum || LeetCode-15

Problem link： https://leetcode.com/problems/3sum/#/description

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

Approach #1 (Brute Force)

Analysis

这道题是求三个数之和，比之前那道Two Sum两数之和要复杂一些，借鉴之前的解题思路。首先我们还是要对原数组进行排序(另一个原因是输出是有序的)，将值和索引存入hashmap中。然后开始两层遍历排序后的数组，这里注意不是遍历到最后一个停止，第一层遍历到倒数第三个就可以了，第二层遍历到倒数第二个就可以了。对于遍历到的数，我们用sum减去这两个数得到一个complement，我们只需要在hashmap中查找是否存在该值即可。需要注意的是，遍历时对重复元素的处理，避免出现重复元素。处理重复元素的关键在于，当i，j第一次遇到重复元素时，允许其遍历。

Code

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

    if (nums.length < 3 || nums == null) {
        return result;
    }

    Arrays.sort(nums); // 数组排序
    int sum = 0;
    Map<integer integer=""> map = new HashMap<>(); // 插入代码出错

    for (int i = 0; i < nums.length; i++) { // 将数组存入hashmap
        map.put(nums[i], i);
    }

    for (int i = 0; i < nums.length - 2; i++) {
        if (i==0 || nums[i] != nums[i - 1]) { // 处理第一层遍历nums[i]的重复
            for (int j = i + 1; j < nums.length - 1; j++) {
                int complement = sum - nums[i] - nums[j];
                if (map.containsKey(complement) && map.get(complement) > j) {
                    List<integer> list = new ArrayList<integer>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(complement);
                    result.add(list);
                }
                while(nums[j] == nums[j + 1] && j < nums.length - 2){
                    j++; //处理第二层遍历nums[j]的重复
                }
            }
        }
    }
    return result;
}

Complexity

时间复杂度：O(n^2)

空间复杂度：O(1)O(n)

Approach #2 (Sorting With Two Pointers)

Analysis

Three Sum问题是Two Sum问题的升级，可以利用Two Sum问题的二分查找法来解决此问题。需要注意的是，Three Sum需要解决duplicate(重复)问题，3个数相加返回数值而不是它的index。首先，同样还是先对数组进行排序。然后，从索引0开始到倒数第三个位置（num.length-3)进行遍历，假定nums[i]就是第一个加数，然后从i+1的位置开始，利用二分查找(low、high指针)进行Two Sum问题的运算。

Code

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

    if (nums.length < 3 || nums == null) {
        return result;
    }
    Arrays.sort(nums); //数组排序

    for (int i = 0; i < nums.length - 2; i++) {
        if(i == 0 || nums[i] != nums[i - 1]){ // 处理nums[i]的重复
            int low = i + 1;
            int high = nums.length - 1;

            while(low < high) {
                int sum = nums[i] + nums[low] + nums[high];
                if (sum == 0) {
                    List<integer> list = new ArrayList<integer>();
                    list.add(nums[i]);
                    list.add(nums[low]);
                    list.add(nums[high]);
                    result.add(list);
                    low++;
                    high--;

                    while (low < high && nums[low] == nums[low - 1]) {
                        low++; //处理nums[low]的重复
                    }

                    while (low < high && nums[high] == nums[high + 1]) {
                        high--; //处理nums[high]的重复
                    }
                } else if (sum > 0) {
                    high--;
                } else
                    low++;
            }
        }
    }
    return result;
}

Complexity

时间复杂度：O(n^2)

空间复杂度：O(1)取决于排序算法

Approach #3 (HashSet)

Analysis

在这个问题中，我们需要输出非重复元素的结果，可以联想到利用hashset来处理这类问题。当找到一个3sum==0的情况时，判断是否在结果hashset中出现过，没有出现过则添加(利用hashset的value唯一性）。因为结果不唯一，此时不能停止，应该继续搜索，low和high指针同时挪动。

Code

public List<List<integer>> threeSum(int[] nums) {
    List<List<integer>> result = new ArrayList<List<integer>>();
    if (nums.length < 3 || nums == null) {
        return result;
    }

    HashSet<List<integer>> hash = new HashSet<List<integer>>();
    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 2; i++) {
        //这种处理重复元素的方式比较容易理解
        if(i > 0 || nums[i] == nums[i - 1])
            continue;
        int low = i + 1;
        int high = nums.length - 1;

        while(low < high){
            int sum = nums[i] + nums[low] + nums[high];
            if (sum == 0) {
                List<integer> list = new ArrayList<integer>();
                list.add(nums[i]);
                list.add(nums[low]);
                list.add(nums[high]);
                if (!hash.contains(list)) {
                    hash.add(list);
                    result.add(list);
                }
                low++;
                high--;
            } else if (sum < 0) {
                low++;
            } else
                high--;
            }
    }
    return result;
}

Complexity

时间复杂度：O(n^2)

空间复杂度：O(1)O(n)