阅读目录
- 1. 题目
- 2. 解题思路
- 3. 代码实现
1. 题目
2. 解题思路
首先我们对数组进行从小到大排序,然后遍历数组 [ 0 , n u m s . s i z e ( ) − 3 ] [0,nums.size()-3] [0,nums.size()−3] 作为三元组中的 a a a,由于三元组的索引互不相同,所以余下的 b b b 和 c c c 我们则只能从 a a a 后面的元素中取,而且 b b b 和 c c c 的索引也不能相同。
假设 a a a 取的是第 i i i 个元素,那么我们让 b b b 首先指向第 i + 1 i+1 i+1 个元素, c c c 首先指向第 n u m s . s i z e ( ) − 1 nums.size()-1 nums.size()−1 个也即最后一个元素。这时候,我们检查 a + b + c a+b+c a+b+c 的和与零的关系。
- 如果二者正好相等,我们保存这个三元组,同时让 b b b 向右移动一步,或者让 c c c 向左移动一步;
- 如果和小于零,只能让 b b b 向右移动一步;
- 如果和大于零,则只能让 c c c 向左移动一步。
同时,结果中不能包含重复的三元组,所以 a , b , c a, b,c a,b,c 更新的时候我们都要确保它们不与上一次的值相同。
排序的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn),求和时,最外层遍历 a a a 的时间复杂度为 O ( n ) O(n) O(n),内层遍历 b b b 和 c c c 正好把数组访问一遍,时间复杂度也为 O ( n ) O(n) O(n),所以求和的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。所以,整体算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2),空间复杂度为 O ( 1 ) O(1) O(1)。
3. 代码实现
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int> > ret;
sort(nums.begin(), nums.end());
int last = nums[0] - 1; // 上一个a,初始化为不和nums[0]相等即可
for (int i = 0; i < nums.size()-2; ++i) {
if (nums[i] == last) {
continue;
}
int first = i + 1;
int first_last_num = nums[first] - 1; // 上一个b,初始化为不和nums[first]相等即可
int second = nums.size() - 1;
int second_last_num = nums[second] + 1; // 上一个c,初始化为不和nums[second]相等即可
while (first != second) {
if (nums[first] == first_last_num) {
++first;
continue;
}
if (nums[second] == second_last_num) {
--second;
continue;
}
int sum = nums[i] + nums[first] + nums[second];
if (sum == 0) {
ret.push_back({nums[i], nums[first], nums[second]});
first_last_num = nums[first++]; // 更新上一次的b
second_last_num = nums[second]; // 更新上一次的c
} else if (sum < 0) {
++first;
} else {
--second;
}
}
last = nums[i]; // 更新上一次的a
}
return ret;
}
};