2
JS 双指针解决三数、四数之和
source link: https://blog.51cto.com/u_13961087/5146410
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
JS 双指针解决三数、四数之和
原创双指针从广义上来说，是指用两个变量在线性结构上遍历而解决的问题。狭义上说，
- 对于数组，指两个变量在数组上相向移动解决的问题；
- 对于链表，指两个变量在链表上同向移动解决的问题，也称为「快慢指针」问题。
双指针算法通常不难，双指针算法是基于暴力解法的优化，它是很好的学习算法的入门问题。
本篇带来两道相似的、有递进关系的“双指针”算法题。
冲就完事了吼~~
“最接近的三数之和”
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入： nums = [0,0,0], target = 1
输出： 0
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入： nums = [0,0,0], target = 1
输出： 0
双指针解法：
数组先升序排序，初始化一个最小和；遍历数组，定义双指针，如果当前和更接近，更新最小值；根据当前三数之和和target的关系，移动指针；若在遍历过程中，三数之和等于target，直接返回当前的和即可。
const threeSumClosest = (nums, target) => {
// 升序排序
nums.sort((a, b) => a - b);
// 初始化一个最小值
let min = Infinity;
const len = nums.length;
for (let i = 0; i < len; i++) {
// 定义左右指针
let [left, right] = [i + 1, len - 1];
while (left < right) {
// 当前三数之和
const sum = nums[i] + nums[left] + nums[right];
// 如果当前和更接近，更新最小值
if (Math.abs(sum - target) < Math.abs(min - target)) {
min = sum;
}
// 根据sum和target的关系，移动指针
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
// sum和target相等，直接返回sum，肯定是最小的了
return sum;
}
}
}
// 遍历结束，返回最接近的和
return min;
};
// 升序排序
nums.sort((a, b) => a - b);
// 初始化一个最小值
let min = Infinity;
const len = nums.length;
for (let i = 0; i < len; i++) {
// 定义左右指针
let [left, right] = [i + 1, len - 1];
while (left < right) {
// 当前三数之和
const sum = nums[i] + nums[left] + nums[right];
// 如果当前和更接近，更新最小值
if (Math.abs(sum - target) < Math.abs(min - target)) {
min = sum;
}
// 根据sum和target的关系，移动指针
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
// sum和target相等，直接返回sum，肯定是最小的了
return sum;
}
}
}
// 遍历结束，返回最接近的和
return min;
};
“四数之和”
给你一个由 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]]
输入：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]]
双指针解法：
先给数组从小到大排序，然后双指针lo和hi分别在数组开头和结尾，这样就可以控制nums[lo]和nums[hi]这两数之和的大小；如果你想让它俩的和大一些，就让lo++，如果你想让它俩的和小一些，就让hi--。
基于两数之和可以得到一个万能函数nSumTarget，具体思路可见题解 一个函数秒杀 2Sum 3Sum 4Sum 问题'
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
// 先排序
nums.sort((a, b) => a - b);
/*
注意：调用这个函数之前一定要先给 nums 排序
n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和
*/
const nSumTarget = (nums, n, start, target) => {
let size = nums.length;
let res = [];
// 至少是 2Sum，且数组大小不应该小于 n
if (n < 2 || size < n) return res;
// 2Sum 是 base case
if (n == 2) {
// 双指针那一套操作
let lo = start,
hi = size - 1;
while (lo < hi) {
let sum = nums[lo] + nums[hi];
let left = nums[lo],
right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
} else {
res.push([left, right]);
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
} else {
// n > 2 时，递归计算 (n-1)Sum 的结果
for (let i = start; i < size; i++) {
let sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
for (let arr of sub) {
arr.push(nums[i]);
res.push(arr);
}
while (i < size - 1 && nums[i] == nums[i + 1]) i++;
}
}
return res;
};
// n 为 4，从 nums[0] 开始计算和为 target 的四元组
return nSumTarget(nums, 4, 0, target);
};
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
// 先排序
nums.sort((a, b) => a - b);
/*
注意：调用这个函数之前一定要先给 nums 排序
n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和
*/
const nSumTarget = (nums, n, start, target) => {
let size = nums.length;
let res = [];
// 至少是 2Sum，且数组大小不应该小于 n
if (n < 2 || size < n) return res;
// 2Sum 是 base case
if (n == 2) {
// 双指针那一套操作
let lo = start,
hi = size - 1;
while (lo < hi) {
let sum = nums[lo] + nums[hi];
let left = nums[lo],
right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
} else {
res.push([left, right]);
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
} else {
// n > 2 时，递归计算 (n-1)Sum 的结果
for (let i = start; i < size; i++) {
let sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
for (let arr of sub) {
arr.push(nums[i]);
res.push(arr);
}
while (i < size - 1 && nums[i] == nums[i + 1]) i++;
}
}
return res;
};
// n 为 4，从 nums[0] 开始计算和为 target 的四元组
return nSumTarget(nums, 4, 0, target);
};
- 赞
- 收藏
- 评论
- 分享
- 举报
上一篇：删除有序数组中的重复项~~
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK