双指针
解题思路
对数组进行升序排序，使用三个指针 i、j 和 k 分别代表要找的三个数，通过枚举 k 确定第一个数，另外两个指针 i、j 分别从左边 k + 1 和右边 n - 1 往中间移动，找到满足
nums[i] + nums[j] + nums[k] == 0的所有组合；j 和 k 指针的移动逻辑，分情况讨论
sum = nums[i] + nums[j] + nums[k]：
sum > 0：k 左移，使 sum 变小；sum < 0：j 右移，使 sum 变大；sum = 0：找到符合要求的答案，存起来；如果
nums[k] > 0那么后面的两个数一定都是大于 0 的，肯定无法满足nums[i] + nums[j] + nums[k] == 0，则直接跳过；还要去除重复结果：
nums[k] === nums[k−1]则说明该数字重复，会导致结果重复，所以应该跳过；- 当
sum == 0时，nums[i] === nums[i+1]则会导致结果重复，应该跳过，i++；- 当
sum == 0时，nums[j] == nums[j−1]则会导致结果重复，应该跳过，j−−；
复杂度
-
时间复杂度
O(N^2)：数组排序O(NlogN)，遍历数组+双指针遍历O(N^2)，总体O(NlogN) + O(N^2)； -
空间复杂度
O(1)；
代码实现
var threeSum = function (nums) {
const res = [];
if (nums.length < 3) return res;
// 1. 数组排序
nums.sort((a, b) => a - b);
let i, j;
// 2. 固定一个指针，另外两个指针根据求和的大小，向内收缩
for (let k = 0; k < nums.length - 2; k++) {
// - nums[k] === nums[k−1] 则说明该数字重复，会导致结果重复，所以应该跳过
// - nums[k] > 0 那么后面的两个数一定都是大于 0 的，无法满足 `nums[i] + nums[j] + nums[k] == 0`，则直接跳过；
if (nums[k] > 0 || nums[k] == nums[k - 1]) continue;
i = k + 1;
j = nums.length - 1;
while (i < j) {
if (nums[k] + nums[i] + nums[j] > 0) {
j--;
} else if (nums[k] + nums[i] + nums[j] < 0) {
i++;
} else {
res.push([nums[k], nums[i], nums[j]]);
// 去掉重复情况
while (i < j && nums[i + 1] == nums[i]) i++;
while (i < j && nums[j - 1] == nums[j]) j--;
i++;
j--;
}
}
}
return res;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 11. 盛最多水的容器
上一篇
评论
