15.三数之和


题目:三数之和

给你一个包含n个整数的数组nums,判断nums中是否存在三个元素a,b,c,使得a + b + c = 0?请你找出所有和为0且不重复的三元组。

注意:答案中不可以包含重复的三元组。

  • 示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
  • 示例 2:
输入:nums = []
输出:[]
  • 示例 3:
输入:nums = [0]
输出:[]
  • 提示:
0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

思路1

先固定一个数i,然后对另外两个数使用双指针,找到两个数之和等于-nums[i]
定义一个HashSet,把结果三元组存放进HashSet中来去重,最后再把HashSet转化为ArrayList,返回一个ArrayList

  • 时间复杂度:O(n²)
  • 空间复杂度:O(n)

代码

public List<List<Integer>> threeSum(int[] nums) { // 总时间复杂度:O(n²)
    // 用set存,可以去重
    Set<List<Integer>> set = new HashSet<>();  // 空间复杂度:O(n)
    Arrays.sort(nums); // 时间复杂度O(nlog₂n)
    for (int i = 0; i < nums.length; i++) { // 时间复杂度O(n²)
        int left = i + 1;
        int right = nums.length - 1;
        int target = -nums[i];
        while (left < right) { // 时间复杂度O(n)
            int sum = nums[left] + nums[right];
            if (sum == target) {
                set.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return new ArrayList<>(set);  // 空间复杂度:O(n)
}

思路2

先固定一个数i,然后对另外两个数使用双指针,找到两个数之和等于-nums[i]
再手动去重,把结果三元组存放进ArrayList,返回ArrayList,可以使空间复杂度降到O(n)。

  • 时间复杂度:O(n²)
  • 空间复杂度:O(n)

代码

public List<List<Integer>> threeSum(int[] nums) { // 总时间复杂度O(n²)
    if (nums == null || nums.length < 3) {
        return new ArrayList<>();
    }
    List<List<Integer>> list = new ArrayList<>(); // 空间复杂度:O(n)
    Arrays.sort(nums); // 时间复杂度O(nlog₂n)
    for (int i = 0; i < nums.length; i++) { // 时间复杂度O(n²)
        if (nums[i] > 0) {
            break; // 第一个数大于 0,后面的数都比它大,肯定不成立了
        }
        // 去掉重复情况
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int left = i + 1;
        int right = nums.length - 1;
        int target = -nums[i];
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 现在要增加 left,减小 right,但是不能重复
                // 当左右指针扫描到与上一个相等的时候,直接跳过
                while (left < right && nums[left] == nums[++left]) {
                }
                while (left < right && nums[right] == nums[--right]) {
                }
            } else if (sum < target) {
                // 当左指针扫描到与上一个相等的时候,直接跳过
                while (left < right && nums[left] == nums[++left]) {
                }
            } else {
                // 当右指针扫描到与上一个相等的时候,直接跳过
                while (left < right && nums[right] == nums[--right]) {
                }
            }
        }
    }
    return list;
}

文章作者: cxyexe
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 cxyexe !
  目录