当前位置 博文首页 > Linux猿：LeetCode面试必备100题：3Sum 数组中查找三个和为零的
作者：Linux猿
简介：CSDN博客专家，C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
关注专栏：LeetCode面试常考100题?（优质好文持续更新中……）
给定一个整数数组 nums，返回所有的三元组 [nums[i], nums[j], nums[k]] 使得 i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0。
注意：解决方案集中不能包含重复的三元组。
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
一句话来说就是：先确定第一个数，然后查找另外两个数的和等于第一个数的相反数即可。
详细分析：先将数组从小到大排序（用于查找另外两个数），然后依次遍历数组，先确定第一个数 nums[k]，然后在这个数后面查找两个数的和是第一个数的相反数（这样三个数相加和为 0）。那么，接下来就是查找另外两个数啦！只需要对排序后的数组，使用两个指针从数组两头（这里指 k+1 ~ n-1）向中间遍历即可。
剪枝操作：
（1）nums[k] > 0 ，遍历数组结束，因为后面所有的数都为正数，没有三个数相加等于0的组合；
（2）k > 0 时，nums[k] == nums[k-1]，不处理，因为当前数 nums[k] 和前一个数相同，会找到重复的；?
时间复杂度：遍历数组的时间复杂度为 O(n)，每次查找另外两个数的时间复杂度是O(n)，因为两个是嵌套的，时间复杂度要相乘，所以总的时间复杂度为O(n^2)。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret; // 存储返回值
sort(nums.begin(), nums.end()); //数组排序
for (int k = 0; k < nums.size(); ++k) { //依次遍历
if (nums[k] > 0) break; //后面都是正数就不考虑了
if (k > 0 && nums[k] == nums[k - 1]) continue; //相等于会重复也不考虑
int target = -nums[k]; //查找 k + 1 ~ nums.size() - 1 中两个数的和等于 -nums[k]
int i = k + 1, j = nums.size() - 1;
while (i < j) {
if (nums[i] + nums[j] == target) {
ret.push_back({nums[k], nums[i], nums[j]});
while (i < j && nums[i] == nums[i + 1]) ++i;
while (i < j && nums[j] == nums[j - 1]) --j;
++i; --j;
} else if (nums[i] + nums[j] < target) ++i;
else --j;
}
}
return ret;
}
};3Sum
cs?关注专栏：LeetCode面试常考100题?（优质好文持续更新中……）
