15. 三数之和
描述
- 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
- 注意：答案中不可以包含重复的三元组。
示例
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路
- 暴力解法，O(n^3)的复杂度，注意利用do while 去除重复的元素。
- 两指针求和，将题目从求三数之和等于 0. 转换为求 a + b = -c, 即求数组中两数之和等于目标数。此处可以将数组排序，然后两指针一头一尾求解。(参考)
Tips
- 化繁为简，将复杂的问题转换为熟悉的小问题。
- 写出暴力解法，然后通过转换降低复杂度。将大的问题分解为小的。如本题，确定一个数后，要求另外两数之和等于 -c，这样如果能将这部分的复杂度降下来，就能将整体的复杂度降低下来了。
- 实现的时候要注意删减枝叶，如本题利用do while / continue 来解决去重的问题，比全部加进去后再判断就要好的多。
class Solution_15_01 {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
int size = nums.size();
for (int i = 0; i < size;) {
for (int j = i + 1; j < size;) {
for (int k = j + 1; k < size;) {
if (nums[i] + nums[j] + nums[k] == 0) {
vector<int> tmp;
tmp.push_back({nums[i], nums[j], nums[k]});
ret.push_back(tmp);
}
do {
++k;
} while (k < size && nums[k - 1] == nums[k]);
}
do {
++j;
} while (j < size && nums[j - 1] == nums[j]);
}
do {
++i;
} while (i < size && nums[i - 1] == nums[i]);
}
return ret;
}
};
class Solution_15_02 {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
int size = nums.size();
for (int i = 0; i < size - 2;) {
if (nums[i] > 0) break; // 此处不能 >= 要考虑 0.0.0 的情况
int target = 0 - nums[i];
int j = i + 1;
int k = size - 1;
while (j < k) {
if (nums[j] + nums[k] < target) {
++j;
} else if (nums[j] + nums[k] > target) {
--k;
} else {
vector<int> tmp;
tmp.push_back({nums[i], nums[j], nums[k]});
ret.push_back(tmp);
do {
++j;
} while (j < k & nums[j - 1] == nums[j]);
do {
--k;
} while (j < k & nums[k + 1] == nums[k]);
}
}
do {
++i;
} while (i < size & nums[i - 1] == nums[i]);
}
return ret;
}
};
// 与解法2的思路一致，只是实现不同，附在此处供参考
class Solution_15_03 {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> rs;
if (nums.size() == 0) return rs;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
if (nums[i] > 0) return rs;
if (i != 0 && nums[i] == nums[i - 1]) continue;
int tmpTarget = 0 - nums[i];
int beg = i + 1, end = nums.size() - 1;
while (beg < end) {
if (nums[beg] + nums[end] == tmpTarget) {
rs.push_back({nums[i], nums[beg], nums[end]});
while (beg < end - 1 && nums[end] == nums[end - 1]) end--;
end--;
} else if (nums[beg] + nums[end] > tmpTarget)
end--;
else
beg++;
}
}
return rs;
}
};
