Leetcode 15
暴力只需要三重循环,然而我们知道 n^2 的复杂度一般我们就已经不能接受了,这里就不实现了。
但是我们可以利用双指针去求解。
由于原数组本身无序,我们可以事先最一下排序,这有助于我们利用有序的性质,使用双指针。
基本思路是,固定第一个位置的数字,随后两个指针分别指向下一个数字,和末尾的数字。
如果它们的和小了,那就移动第一个指针;如果大了,那就移动末尾的指针。
由于可能存在重复的数字,而答案要求我们不包含重复,我们可以在移动左指针时判断,如果移动后依然是原数字,就继续移动。我高亮了关键代码。
上一步,我犯过了一个错误,我试图在 while
循环的一开始做这个操作,这会导致我们漏掉一些三元组。因为我们过于提前移动了,虽然是重复的数字,但是这个数字是有可能被右指针使用的,所以会导致漏答案。
而等我们得到一次答案后,下一次又遇到了同样的值,我们这时候去快速跳过重复,这样是安全的了。
当然,我们完全可以先忽略去重的事情,在返回前做去重操作,但这无疑会增加代码量。
额外的,我们可以做亮点小优化:
i + 1
和 i + 2
时,我们可以提前跳出循环结束。nums.length - 1
和 nums.leng - 2
时,我们可以提前跳出循环。同样,上面两步我也高亮了代码。
function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const ans: number[][] = []
for (let i = 0; i < nums.length; i++) {
if (nums[i] === nums[i-1]) {
continue;
}
const target = -nums[i];
let left = i + 1;
let right = nums.length - 1;
if (nums[left] + nums[left+1] > target) {
continue
}
if (nums[right] + nums[right-1] < target) {
continue
}
while (left < right) {
if (nums[left] + nums[right] < target) {
left++;
} else if (nums[left] + nums[right] > target) {
right--;
} else {
ans.push([-target, nums[left], nums[right]])
left++;
while (nums[left] === nums[left-1]) {
left++;
}
right--;
while (nums[right] === nums[right+1]) {
right--;
}
}
}
}
return ans
};