80 lines
2.4 KiB
C++
80 lines
2.4 KiB
C++
#include "s0015_3sum.hpp"
|
|
|
|
// 思路一：
|
|
// 遍历一次，创建一个哈希表
|
|
// 双重遍历，找 - nums[i] - nums[j] 是否存在于哈希表中
|
|
// 去重的方式：
|
|
// 对于每个找到的序列，先排序，如果不存在则添加到结果中。
|
|
|
|
vector<vector<int>> S0015::threeSum1(vector<int>& nums) {
|
|
unordered_map<int, int> map;
|
|
vector<vector<int>> result;
|
|
int len = nums.size();
|
|
if (len == 0) {
|
|
return result;
|
|
}
|
|
for (int i{0}; i < len; i++) {
|
|
map[nums.at(i)] = i;
|
|
}
|
|
for (int i{0}; i < len; i++) {
|
|
for (int j{0}; j < len; j++) {
|
|
if (i == j) {
|
|
continue;
|
|
} else {
|
|
if (map.count(0 - nums.at(i) - nums.at(j)) != 0) {
|
|
if (i == map[0 - nums.at(i) - nums.at(j)] ||
|
|
j == map[0 - nums.at(i) - nums.at(j)]) {
|
|
continue;
|
|
} else {
|
|
vector<int> v{nums.at(i), nums.at(j), 0 - nums.at(i) - nums.at(j)};
|
|
sort(v.begin(), v.end());
|
|
// push if not exist
|
|
if (std::find(result.begin(), result.end(), v) == result.end()) {
|
|
result.push_back(v);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
// 思路二：双指针
|
|
// 先对整个数组排序，然后固定一个数 a ，然后 b, c 从两边往中间靠。
|
|
vector<vector<int>> S0015::threeSum2(vector<int>& nums) {
|
|
int n = nums.size();
|
|
sort(nums.begin(), nums.end());
|
|
vector<vector<int>> ans;
|
|
// 枚举 a
|
|
for (int first = 0; first < n; ++first) {
|
|
// 需要和上一次枚举的数不相同
|
|
if (first > 0 && nums[first] == nums[first - 1]) {
|
|
continue;
|
|
}
|
|
// c 对应的指针初始指向数组的最右端
|
|
int third = n - 1;
|
|
int target = -nums[first];
|
|
// 枚举 b
|
|
for (int second = first + 1; second < n; ++second) {
|
|
// 需要和上一次枚举的数不相同
|
|
if (second > first + 1 && nums[second] == nums[second - 1]) {
|
|
continue;
|
|
}
|
|
// 需要保证 b 的指针在 c 的指针的左侧
|
|
while (second < third && nums[second] + nums[third] > target) {
|
|
--third;
|
|
}
|
|
// 如果指针重合，随着 b 后续的增加
|
|
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
|
|
if (second == third) {
|
|
break;
|
|
}
|
|
if (nums[second] + nums[third] == target) {
|
|
ans.push_back({nums[first], nums[second], nums[third]});
|
|
}
|
|
}
|
|
}
|
|
return ans;
|
|
}
|