leetcode题解-15三数之和
程序员文章站
2022-07-14 17:27:38
...
三数之和:link
1.题目分析
首先想到的是固定两个数最后去确定第三个数,时间复杂度为O(n2logn),最好的方法是固定一个然后使用twoSum的方法去寻找那两个,时间复杂度为O(n2),注意事项为要跳过重复的。
2.示例代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
for (int i = 0; i < (int)nums.size() - 2; ++i) {
if (i == 0 || nums[i] != nums[i - 1]) {
//find the combination
int lo = i + 1, hi = nums.size() - 1;
int twoSum = -nums[i];
while (lo < hi) {
if (nums[lo] + nums[hi] == twoSum) {
ret.push_back({ nums[i], nums[lo], nums[hi] });
while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
lo++; hi--;
}
else if (nums[lo] + nums[hi] < twoSum) {
lo++;
}
else {
hi--;
}
}
}
else {
//skip the duplications
continue;
}
}
return ret;
}
};
上一篇: 【LeetCode题解】18.四数之和
下一篇: day4 作业