LeetCode015-3Sum

3Sum

Question:

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example1:

Given array nums = [-1, 0, 1, 2, -1, -4],

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

解法代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode015 {

    public static void main(String[] args) {
        int[] nums = new int[]{-1, 0, 1, 2, -1, -4};
        List<List<Integer>> list = new LeetCode015().threeSum(nums);
        System.out.println(list.toString());
        int[] nums1 = new int[]{-2, 1, 1, 1, -1, -4};
        list = new LeetCode015().threeSum(nums1);
        System.out.println(list.toString());
        int[] nums2 = new int[]{};
        list = new LeetCode015().threeSum(nums2);
        System.out.println(list.toString());
        int[] nums3 = new int[]{-1,0,1,2,-1,-4};
        list = new LeetCode015().threeSum(nums3);
        System.out.println(list.toString());
    }
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0) return list;//空数据，直接返回，避免NPE
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 2; i++) {
            if(nums[i] > 0) break;//当nums[i]>0，后续不存在解
            if(nums[nums.length-1] < 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;//防止重复元素
            int k = i + 1;
            int j = nums.length -1;
            int target  = -nums[i];
            while(k < j) {
                if(nums[k] + nums[j] == target) {
                    List<Integer> iList = Arrays.asList(nums[i], nums[k], nums[j]);
                    list.add(iList);
                    //防止重复元素
                    while(k < j && nums[k] == nums[k + 1]) k++;
                    while(k < j && nums[j] == nums[j - 1]) j--;
                    k++;j--;
                } else if(nums[k] + nums[j] < target) {
                    k++;
                } else {
                    j--;
                }
            }
        }
        return list;
    }
}

Output：

[[-1, -1, 2], [-1, 0, 1]]
[[-2, 1, 1]]
[]
[[-1, -1, 2], [-1, 0, 1]]

Time And Space Complexity

Time: 需要循环遍历两次数组，时间复杂度
Space: 不需要使用额外的存储空间，空间复杂度

Tips

• 才开始考虑使用两数之和的方案，进行解决，但是无法排除重复解。
• 然后考虑笨办法，使用三层循环，依次遍历寻找解，时间复杂度为，在数据量较大的测试用例下超时。
  求解超时

//三次循环代码
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0)
            return list;
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        int repeatNum = nums[0];
        for (int i = 0; i < nums.length - 2; i++) {
            if (i != 0 && nums[i] == repeatNum) {
                continue;
            } else {
                repeatNum = nums[i];
            }
            int repeatNum2 = nums[i + 1];
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (j != i + 1 && nums[j] == repeatNum2) {
                    continue;
                } else {
                    repeatNum2 = nums[j];
                }
                for (int m = j + 1; m < nums.length; m++) {
                    int target = 0 - nums[i] - nums[j];
                    if (nums[m] == target) {
                        List<Integer> iList = 
                                        Arrays.asList(nums[i], nums[j], nums[m]);
                        list.add(iList);
                        break;
                    }
                    if (nums[m] > target) {
                        break;
                    }
                }
            }
        }
        return list;
    }
}

• 最终解法分析

1. 对待求解数据排序，排序后让求解时间复杂度从降到成为可能，并且排序数组拥有去除重复解的能力；
2. 对于空数组直接返回防止NPE；
3. 遍历数组从i=0到倒数第三个i=nums.length - 2，其中当nums[i]>0则break，说明数组后续全为正数，不存在三数和为0的情况，同理如果排序后数组最后一个为负数，也break；
4. 当i > 0并且nums[i] == nums[i-1]，说明i-1位置如果存在解，则与i位置的解重复，因此直接continue进入下一个循环；
5. 数组第i个元素值nums[i]，将求解目标调整为在数组i+1到nums.length-1位置中查找是否存在两个元素之和等于-nums[i]。如果此处使用两层循环求解则时间复杂度为，考虑到数组是有序的，定义两个游标，一个从i+1往后遍历，一个从nums.length-1往前遍历，如果两数之和等于-nums[i]则表示找到了解（得到解后需要跳过重复解，原理与第4步相同），如果两数之和小于-nums[i]则前面的游标往后移，加大两数之和的值，否则后面的游标往前移，直到两个游标相遇。这样时间复杂度从降到了。

此题关键点是如何降低复杂度和去除重复解。