学习记录：js算法（十五）：三数之和

文章目录

- 三数之和
- - 我的思路
  - 网上思路
- 总结

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

我的思路
本来想用双指针来写的，但是没有思路，就老规矩，循环
网上思路
双指针

我的思路

var threeSum = function (nums) {let arr = []let len = nums.lengthfor (let i = 0; i < len - 2; i++) {for (let j = i + 1; j < len - 1; j++) {for (let k = i + 2; k < len; k++) {if (nums[i] + nums[j] + nums[k] == 0 && i != j && i != k && j != k) {arr.push([nums[i], nums[j], nums[k]])}}}}arr.forEach(item => {item.sort((a, b) => (a - b))})let b = [...new Set(arr.map(JSON.stringify))].map(JSON.parse)return b
};

讲解

注意一下每次循环的长度就行了，因为 j 从 i 后面一位开始，同时 j 后面还有一个 k，所以范围： i+1 ~ len-1，同理 k 的范围：i+2 ~ len
题目要求去重，但是 使用 new Set([ [1,2] , [1,2] , [2,3] ] )去重不起效果，得将 [ [1,2] , [1,2] , [2,3] ]修改成[ “[1,2]” , “[1,2]” , “[2,3]” ]

网上思路

function threeSum(nums) {nums.sort((a, b) => a - b); // 对数组进行排序const result = [];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 total = nums[i] + nums[left] + nums[right];if (total < 0) {left++; // 和小于0，移动左指针增大和} else if (total > 0) {right--; // 和大于0，移动右指针减小和} else {// 找到一个三元组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--;}}}return result;
}

讲解

排序：使用 sort 方法对数组进行排序。这一步是关键，因为排序后我们可以更容易地避免重复并使用双指针方法。
遍历：通过一个 for 循环遍历每个元素，作为三元组的第一个元素。
外层循环： 遍历每个元素 i，从第一个元素到倒数第三个元素（因为我们需要找到两个其他元素）。
跳过重复： 如果当前元素与前一个元素相同，跳过当前循环。这是为了避免在结果中出现重复的三元组。
双指针：定义两个指针 left 和 right，分别指向当前元素的下一个位置和数组的最后一个位置。
条件判断：根据三数之和的值来调整指针的位置，并在找到符合条件的三元组后，跳过重复的元素。
如果 total < 0，说明需要更大的值，移动 left 指针向右。
如果 total > 0，说明需要更小的值，移动 right 指针向左。
如果 total === 0，说明找到了一个三元组，将其加入到结果数组中。

返回结果：最终返回所有找到的三元组。