三数之和
# 📃 题目描述
题目链接:
- 剑指 Offer II 007. 数组中和为 0 的三个数 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 15. 三数之和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给你一个包含 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]输出:[]
# 🔔 解题思路
# 哈希表
回顾下 1. 两数之和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 和 454. 四数相加 II - 力扣(LeetCode) (leetcode-cn.com) (opens new window),总的思想都是固定一半,然后去找另一半。对于这道题目,找出一个数组中的三个数,我们同样可以固定 a 和 b,去找 c。具体来说,先将这个数组存入 map,然后利用两个 for 循环求出 a 和 b 之和,判断 0-(a+b) 也就是 c 是否在 map 里出现过即可(并且这个 0-(a+b) 还得在 b 的右边))。
具体的细节来说,由于需要避免重复元组,所以我们需要对数组进行一个排序,循环的过程中跳过重复元素。
class Solution {
private final static Integer TARGET = 0;
public List<List<Integer>> threeSum(int[] nums) {
// 存储三元组
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 3) {
return res;
}
// 对数组进行排序
Arrays.sort(nums);
// 将数组存入 map, 相等的值只会放进去一个, i 为下标
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i ++) {
map.put(nums[i], i);
}
// 两层循环固定 a 和 b
// 遍历获得 a
for (int i = 0; i < nums.length; i ++) {
// 若 nums[i] > 0,由于数组已经有序,所以它后面的一定也 > 0,直接返回,那么一定不可能找到第一个数为 nums[i] 且和为 0 的三元组了
if (nums[i] > 0) {
break;
}
// 对 a 进行去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 遍历获得 b
for (int j = i + 1; j < nums.length; j ++) {
// 对 b 进行去重
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int c = TARGET - nums[i] - nums[j];
// 尝试从哈希表中获取第三个数字 c, 若存在,并且第三个数字需要在第二个数字右侧(防止重复)
if (map.containsKey(c) && map.get(c) > j) {
res.add(Arrays.asList(nums[i], nums[j], c));
}
}
}
return res;
}
}
需要注意的就是对 a 和 b 都要进行去重操作:
- 空间复杂度:O(N^2)(如果我们忽略掉用于存储答案的空间,那么该算法的空间复杂度主要来自于排序,额外的排序的空间复杂度为 O(logN))
- 时间复杂度:排序的时间复杂度是 O(nlogn),两层循环处理的时间复杂度是 O(N^2),所以总时间复杂度为 O(N^2)
# 双指针
双指针法做这道题目会更简单。思路如下:
1)对数组进行排序
2)遍历排序后的数组
- 若 nums[i] > 0,由于数组已经有序,所以它后面的一定也 > 0,直接返回
- 对于重复元素,跳过
- 两个指针,左指针 left 指向 i + 1,另一个右指针 right 指向数组的最后一个元素:
- 若 nums[i] + nums[left] + nums[right] = 0,说明这三个就是符合要求的元组。然后 left ++,right -- 寻找新的解(需要注意的是,在移动的过程中,记得进行去重,跳过重复元素)
- 若 nums[i] + nums[left] + nums[right] < 0,left ++
- 若 nums[i] + nums[left] + nums[right] > 0,right --
单层 for 循环固定一个元素,然后用双指针法找剩下的两个元素(前提是数组有序)。
class Solution {
private final static Integer TARGET = 0;
public List<List<Integer>> threeSum(int[] nums) {
// 存储三元组
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 3) {
return res;
}
// 1. 对数组进行排序
Arrays.sort(nums);
// 2. 遍历处理数组
for (int i = 0; i < nums.length; i ++) {
if (nums[i] > 0) {
break;
}
// 跳过重复元素
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 左右指针
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 跳过重复元素
while (left < right && nums[left] == nums[left + 1]) {
left ++;
}
while (left < right && nums[right] == nums[right - 1]) {
right --;
}
// 开始寻找新的解
left ++;
right --;
} else if (sum < 0) {
left ++;
} else {
right --;
}
}
}
return res;
}
}
和哈希表解法的运行时间对比下:
# 💥 复杂度分析
- 空间复杂度:O(N^2)(如果我们忽略掉用于存储答案的空间,那么该算法的空间复杂度主要来自于排序,额外的排序的空间复杂度为 O(logN))
- 时间复杂度:for 循环的时间复杂度 O(N),其中双指针遍历的时间复杂度 O(N),所以是 O(N^2)
# 🍚 加餐
各位思考下,对于这道之前用哈希表做的题 1. 两数之和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window),咱能用双指针吗?
答案是不能的。
因为我们需要遍历一个有序的数组,而题目给的不是一个有序的数组,所以我们需要进行排序。
但是,题目要求返回的是下标,那排序完了下标都乱了。
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~