LeetCode 0015 - 3Sum
# Hints
- 思维 + 双指针扫描
# 前置题目
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given an array nums
of integers, are there elements in nums
such that ? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
# 题意
给定一个长为 的数组,求出所有的三元组 ,满足 。要求返回的结果中没有重复的三元组,且每个三元组内部都是有序的。
# 题解
暴力枚举的做法很显然,时间复杂度为 。
考虑Leetcode 0001中的2-sum问题,如果我们枚举 ,在后半部分求所有的二元组 满足 ,即可将问题转化为2-sum问题,其时间复杂度为 ,因此总的时间复杂度为 。
问题在于难以进行判重。如果直接用set暴力判重,则时间复杂度会劣化到 。虽然这仍然是可以接受的,但我们可以做到更优。
注意到一个事实,我们不能在 的时间内求解3-sum问题,这意味着花费 的时间对数组进行排序是不会影响时间复杂度的。问题转化为在有序数组上求解2-sum问题并去重。
对于有序数组,求解2-sum问题非常简单,很容易想到双指针扫描,时间复杂度仍为 。虽然没有改进,但是关键是对于有序数组我们可以很方便地在求解过程中顺便完成去重。
首先是双指针扫描的细节,我们初始令 ,其中 表示 的下标值。考虑当前两数之和 ,注意到 右移和 左移分别会使得 单调增和单调减,因此如果 ,则 右移,如果 ,则 左移。
因为数组是有序的,所以所有的相等元素都是相邻的。当 或 移动后,如果当前元素和前一元素的数值相等,显然求解的结果会是重复的,我们直接跳过当前元素。在枚举 时也可以用同样的方法去重。这样一来,我们就在求解过程中顺便完成了去重,保证了时间复杂度是最优的。
细节问题:
注意特判 的情况,但我的代码实现其实可以不需要特判。
注意2-sum的双指针扫描实现中,递进和去重的代码细节,容易出现越界、死循环、遗漏答案等错误。
# AC代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int> & nums) {
// 特判
if (nums.size() < 3) {
return vector<vector<int>>();
}
// 排序
sort(nums.begin(), nums.end());
// 暴力枚举
vector<vector<int>> res;
for (int i = 0; i < (int)nums.size() - 2; i ++) {
// 去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 求解
vector<vector<int>> vec = twoSum(nums, i, -nums[i]);
// 更新答案
res.insert(res.end(), vec.begin(), vec.end());
}
// 返回
return res;
}
// 求解2-sum问题(有序)
vector<vector<int>> twoSum(vector<int> & nums, int index, int target) {
// 主循环
vector<vector<int>> res;
int left = index + 1, right = (int)nums.size() - 1;
while (left < right) {
// 求和
int sum = nums[left] + nums[right];
// 相等的情况
if (sum == target) {
// 更新答案
res.push_back(vector<int>({nums[index], nums[left], nums[right]}));
// 递进
left ++;
right --;
// 去重
while (left < right && nums[left] == nums[left - 1]) { // && left > 0
left ++;
}
while (left < right && nums[right] == nums[right + 1]) { // && right < (int)nums.size() - 1
right --;
}
} else {
// 递进
if (sum < target) left ++;
if (sum > target) right --;
}
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01