学习记录：js算法（十六）：四数之和
文章目录
- 四数之和
- 我的思路
- 总结
四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
- 0 <= a, b, c, d < n
- a、b、c 和 d 互不相同
- nums[a] + nums[b] + nums[c] + nums[d] == target
- 可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
我的思路
昨天写了三数之和，今天写四数，那肯定要使用不熟练的指针写法了。
网上思路
如上
我的思路
var fourSum = function (nums, target) {nums.sort((a, b) => a - b);const res = new Set();const n = nums.length;for (let i = 0; i < n - 3; i++) {for (let j = i + 1; j < n - 2; j++) {let left = j + 1;let right = n - 1;while (left < right) {const sum = nums[i] + nums[j] + nums[left] + nums[right];if (sum === target) {res.add(`${nums[i]},${nums[j]},${nums[left]},${nums[right]}`);left++;right--;} else if (sum < target) {left++;} else {right--;}}while (j + 1 < n && nums[j] === nums[j + 1]) {j++;}}while (i + 1 < n && nums[i] === nums[i + 1]) {i++;}}return Array.from(res).map(quad => quad.split(',').map(Number));
}
讲解
- 对输入的数组 nums 进行 排序和去重 。是为了后续的双指针操作以及避免重复四元组的出现。
- 外层循环 i 从 0 到 n - 3，目的是 固定第一个数 nums[i] 。内层循环 j 从 i + 1 到 n - 2，目的是 固定第二个数 nums[j]。这样，就有了两个固定的数，接下来要寻找四个数中剩下的两个数。
- 定义两个指针 left 和 right，分别指向 当前固定数 j 之后的第一个元素 和 数组的最后一个元素。然后通过 while (left < right) 循环 来寻找满足条件的四元组。
- 在循环中，需要计算当前四个数的和 sum：
- 如果 sum 等于目标值 target，则将这个四元组添加到 Set 中，并移动 left 和 right 指针，寻找其他可能的组合。
- 如果 sum 小于目标值，说明我们需要更大的数，因此移动 left 指针向右。
- 如果 sum 大于目标值，说明需要更小的数，因此移动 right 指针向左。
- 在每次内层循环结束后，需要跳过重复的元素，以确保不会得到重复的四元组。这个逻辑适用于 外层循环的 i 和内层循环的 j。
- 将 Set 中的字符串转换为数组形式。使用 Array.from(res) 将 Set 转换为数组，然后用 map 方法将每个字符串分割成数字数组。
总结
今天特地用双指针的写法来解题的，说实话，我想了老半天，才在别人的代码下写出来的。。。