15. 三数之和

题目地址(3sum/">15. 三数之和)

https://leetcode.cn/problems/3sum/

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

前置知识

• 双指针法

公司

• 暂无

思路

• 双指针法

关键点

• 1）去重，需要排序然后才方便判断，第一个数和第二个数都需要判断重复，我这里两个去重方法都放在最后
• 2）最精妙之处，还是双指针法，j = i + 1, k = n - 1（末尾）
  • 情况1.nums[j] + nums[k] < target，此时只需要j++即可
  • 情况2.nums[j] + nums[k] > target，此时k--即可
  • 关键问题，k--后，要不要还原k到n-1，答案是不用，因为数组已经排过序了，j++后，想要j,k位置两数之和为target，k必然是一直--

代码

• 语言支持：Java

Java Code:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        if (null == nums || n < 3) {
            return null;
        }
        // 依次将数组的第一个元素作为target，然后在剩下的数组寻找两个之和为target的数
        List<List<Integer>> result = new ArrayList<>();
        // 排序是为了去重方便
        Arrays.sort(nums);
        for (int i = 0; i < n - 2;)  {
            // 双指针法
            int j = i + 1;
            int k = n - 1;
            int target = - nums[i];
            while (j < k) {
                while (j < k && nums[j] + nums[k] > target) {
                    k--;
                }
                // 这里不能少了j < k，否则当j == k时，会一个位置取两次
                if (j < k && nums[j] + nums[k] == target) {
                    result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));  
                }
                j++;
                // 跳过重复的j
                while (j < k && nums[j] == nums[j - 1]) {
                    j++;
                }    
            }
            i++;
            while (i < n - 2 && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return result;
    }
}

Go code:

func threeSum(nums []int) [][]int {
    if (nums == nil || len(nums) < 3) {
        return nil
    }
    n := len(nums)
    // sort标准库
    sort.Ints(nums)
    // 使用make，才能append
    result := make([][]int, 0)
    for i := 0; i < n - 2; {
        j, k, target := i + 1, n - 1, - nums[i]
        for j < k {
            for j < k && nums[j] + nums[k] > target {
                k--
            }

            if j < k && nums[j] + nums[k] == target {
                // append是builtin标准库
                result = append(result, []int{nums[i], nums[j], nums[k]})
            }

            j++
            for j < k && nums[j] == nums[j - 1] {
                j++
            } 
        }
        i++
        for i < n - 2 && nums[i] == nums[i - 1] {
            i++
        }
    }
    return result
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：
• 空间复杂度：就是排序的空间复杂度，如果需要复制，则是