LeetCode 热题 100 之第6题 三数之和（JavaScript篇）leetcode三数之和为0
LeetCode 热题 100 之第6题 三数之和（JavaScript篇）要求找到数组中所有不重复的三元组，使得它们的和为零，可以使用双指针法来解决这个问题，首先排序数组，然后遍历每个元素，并使用双指针在剩余部分查找另外两个数，使得它们的和与当前元素相加为零，这种方法的时间复杂度为 O(n^2)，适用于大部分情况，在 JavaScript 中，可以使用Array.prototype.sort()对数组进行排序，并使用for循环和while循环实现双指针的查找。
LeetCode 热题 100 之第6题 三数之和（JavaScript篇） 描述
LeetCode 热题 100 之第6题，题目名称为“三数之和”，题目要求我们在一个数组中找到所有不重复的三元组，使得这三个数的和为零，每个三元组中的元素按升序排列，给定数组 nums = [-1, 0, 1, 2, -1, -4]，则所有满足条件的三元组为 [-1, -1, 2]、[-1, 0, 1]。
解题思路
解决这个问题的关键在于如何有效地减少搜索空间，避免重复解，一种常见的方法是使用双指针法结合排序,具体步骤如下：
- 排序：首先对数组进行排序，这是解决问题的前提，排序后，相同的元素会相邻,便于后续处理重复元素。
- 遍历：使用三个指针进行遍历，第一个指针从数组的第一个元素开始，第二个和第三个指针分别从第二个和倒数第三个元素开始,向中间靠拢。
- 移动指针：通过移动指针来缩小搜索范围，如果三个数的和等于零，则找到了一个解；如果和小于零，则左移第一个指针以增加总和；如果和大于零,则右移第三个指针以减小总和。
- 跳过重复元素：在遍历过程中，如果发现当前元素与之前元素相同,则跳过以避免重复解。
代码实现（JavaScript）
下面是使用 JavaScript 实现该算法的代码：
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const result = [];
nums.sort((a, b) => a - b); // 对数组进行排序
for (let i = 0; i < nums.length - 2; i++) {
// 跳过重复元素，避免重复解
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1; // 左指针
let right = nums.length - 1; // 右指针
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
// 跳过重复元素，避免重复解
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++; // 和小于零，左移左指针以增加总和
} else {
right--; // 和大于零，右移右指针以减小总和
}
}
}
return result;
};
代码解析
- 排序：
nums.sort((a, b) => a - b);对数组进行升序排序，这是解决问题的前提，因为排序后相同的元素会相邻,便于后续处理重复元素。 - 遍历：
for (let i = 0; i < nums.length - 2; i++)使用第一个指针i从数组的第一个元素开始遍历。left和right分别指向i的下一个位置和数组的最后一个位置,通过移动这三个指针来缩小搜索范围。 - 移动指针：根据当前三个数的和
sum调整指针的位置。sum为零，则找到了一个解；sum小于零，则左移左指针left以增加总和；sum大于零，则右移右指针right以减小总和。 - 跳过重复元素：在遍历过程中，如果发现当前元素与之前元素相同，则跳过以避免重复解，具体实现为：
if (i > 0 && nums[i] === nums[i - 1]) continue;以及在找到解后继续跳过重复元素：while (left < right && nums[left] === nums[left + 1]) left++;和while (left < right && nums[right] === nums[right - 1]) right--;。
时间复杂度分析
该算法的时间复杂度为 O(n^2)，n 是数组的长度，这是因为我们使用了三个指针进行遍历和移动，每个指针最多遍历 n 个元素，由于我们跳过了重复元素，实际运行时间会比 O(n^3) 更优，空间复杂度为 O(1),除了返回结果外没有使用额外的空间。