[leetcode] 15. 三数之和

题目描述

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

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

解题方法

排序 + 遍历

以下部分请结合代码进行理解。首先，我们把数组按照从小到大进行排序。然后，我们设$i$为最外层的遍历指针，从数组头开始遍历；$j$为第二层的遍历指针，从$i+1$的位置开始遍历。当$nums[i]+nums[j]<=0$时，才存在一个数字$nums[k]$，使得$nums[i]+nums[j]+nums[k]==0$。怎么查找这个$nums[k]$呢？

笨方法是设置第三层遍历，从$j+1$的位置开始查找，直到找到$nums[k]$，使得$nums[i]+nums[j]+nums[k]>=0$时，遍历结束。当三数相加等于0时，这三个数构成一个三元组，否则没有合适的三元组，再从第二层的遍历指针往后移动一位开始下一次遍历。

既然说是笨方法，那当然还有一种更快的方式查找$nums[k]$，那就是先用一个$map$将数组中出现的数字和它最后一次出现的下标索引分别作为$key$和$value$存起来。我们查找$nums[k]$时，只需查找这个数字是否在这个$map$中，以及这个数字存在时，需要检查它的下标索引是否大于$j$，防止找到的这个数字跟$nums[j]$在同一个位置。

说完上面的优化查找，再说一个小优化。题目中提出答案中不可以包含重复的三元组，当我们遍历数组时，如果我们遍历的数字跟上一次遍历的数字相等，即$nums[i+1]==nums[i]$或者$nums[j+1]==nums[j]$，那么从$i+1$或者$j+1$处进行遍历时，必然会找到跟上次遍历重复的元组。所以我们可以跳过$i+1$或者$j+1$，直接从$i+2$或者$j+2$的位置开始遍历，此时也需要判断是否$nums[i+2]==nums[i+1]$或者$nums[j+2]==nums[j+1]$，依次类推。所以每次遍历之前，我们需要判断此时遍历到的数字与上一次遍历的数字是否相等，若相等，则跳到后面的位置。

java代码

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 符合条件的所有三元组集合
        List<List<Integer>> list = new ArrayList<>();
        // 前两个数字相加后，便于查找相加为0第三个数字是否存在
        Map<Integer, Integer> map = new HashMap<>();

        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);

        }
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i != 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if (nums[i] + nums[j] > 0) {
                    break;
                }
                if (map.containsKey(-nums[i] - nums[j]) && map.get(-nums[i] - nums[j]) > j) {
                    List<Integer> list1 = new ArrayList<>();
                    list1.add(nums[i]);
                    list1.add(nums[j]);
                    list1.add(-nums[i] - nums[j]);
                    list.add(list1);
                }

            }
        }
        return list;
    }
}

时间复杂度：$O(N^2)$，排序的时间复杂度是$O(NlogN)$，遍历的时间复杂度是$O(N^2)$，两者相加还是$O(N^2)$。
空间复杂度：$O(N)$，用到了$map$存储数字和对应位置。

相似题目

[leetcode] 1. 两数相加

---

• 个人公众号
  
• 个人小游戏