使用 JavaScript 解答 LeetCode 第 1/15/18 题,两数之和、三数之和、四数之和。
N 数之和问题的解题思路是一脉相承的,从最基础的两数之和开始,逐步解决更复杂的计算。
两数之和
原题链接
本题是 LeetCode 题库第 1 题,由此访问。
题目描述
给定一个整数数组 nums
和一个目标值 target
,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路
两数之和问题有多种解题方法,暴力法是其中最简单的。暴力法的基本思路是,两次遍历数组,将两次遍历过程中取得的数字依次相加,如结果等于 target
值,返回两数对应下标。暴力法时间复杂度为 O(n^2)
,最差情况下需要两次完整的遍历才能取得结果。
我们需要对这一问题尽可能简化,使用哈希表对遍历结果进行存储,可以将两次遍历改为只需一次,时间复杂度控制在 O(n)
水平。根据题目描述,两数之和等于 target
,那么在遍历过程中已经指定了其中一个数的下标(设为 n),另一个数则表示为 target-nums[n]
。在哈希表中 target-n
键的值设为当前遍历值的下标,当遍历到后续的数字时,查询哈希表即可了解对应数的下标位置。将两个下标位置存储在数组内返回,即是最终答案。
AC 样例
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const hash = {};
for(let x = 0; x < nums.length; x++) {
if(hash[nums[x]] !== undefined) return [hash[nums[x]], x];
else hash[target-nums[x]] = x;
}
};
三数之和
原题链接
本题是 LeetCode 题库第 15 题,由此访问。
题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a
、b
、c
,使得 a + b + c = 0
?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
解题思路
三数之和可以理解为是两数之和的复杂版本,暴力法的时间复杂度达到了 O(n^3)
。参考题目描述,数字 a
、b
、c
之间存在 a+b+c=0
的关系,可以简化为 b+c=-a
。按照这一思路,可以将三重遍历简化为一次遍历+一次两数之和计算。
首先对数组进行升序排序。其次遍历数组,设为数字 a
,在剩下的范围内求取 b
和 c
,判断其是否符合 b+c=-a
的关系。选取 b
、c
的过程中为提高效率,使用双指针,分别从数组内 a
之后的范围起止点开始,依次枚举两端数据进行比较。若两数之和大于 -a
,则 c
端数字过大,向左移动后再判断;若两数之和小于 -a
,则 b
端数字过小,向右移动后再判断;若两数之和等于 -a
,则符合题目要求,以数组形式存储于最终结果数组。
当所有数字 a
,及其 b
、c
遍历完成后,将最终结果二维数组返回。
升序排序使用快速排序算法,时间复杂度为 O(nlogn)
;求取 b
、c
过程中采用双指针方法,另根据题目要求避免重复数据产生,每次求取 b
、c
的最大搜索次数小于数组规模,这一过程时间复杂度为 O(n)
;对数字 a
采用一次遍历方法,时间复杂度为 O(n)
。综上所述,本算法时间复杂度控制在 O(n^2)
。
AC 样例
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const res = [];
// 数组排序
nums = nums.sort((a, b) => a - b);
// 遍历 a
for(let x = 0; x < nums.length; x++) {
// 重复 a 的排除
if (x > 0 && nums[x] == nums[x-1]) continue;
// 设 c 在 nums 最尾端
let z = nums.length - 1;
const target = -nums[x];
for(let y = x + 1; y < nums.length; y++) {
// 重复 b 的排除
if(y > x + 1 && nums[y] == nums[y-1]) continue;
// 保持 c 始终大于 b
while(z > y && nums[z] + nums[y] > target) z--;
// c b 一致时中止
if (z == y) break;
if(nums[y] + nums[z] == target) res.push([nums[x], nums[y], nums[z]]);
}
}
return res;
};
四数之和
原题链接
本题是 LeetCode 题库第 18 题,由此访问。
题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c,d
,使得 a + b + c + d
的值与 target
相等?找出所有满足条件且不重复的四元组。
注意:答案中不可以包含重复的四元组。
示例:
给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。
满足要求的四元组集合为:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
解题思路
四数之和问题和三数之和类似,在暴力法情况下时间复杂度可达 O(n^4)
,这里我们将其简化,可得数字关系为 (c+d)=target-(a+b)
,即将四个数的匹配过程改为两次遍历+一次两数之和计算,整体时间复杂度可控制在 O(n^3)
水平。
首先对数组进行升序排序,之后遍历 a
、b
,在遍历过程中需要注意去重。在一次循环中,数字 a
、b
确定的情况下,求取符合条件的数字 c
、d
。基本思路与三数之和一致。
对数组排序使用快速排序算法,时间复杂度 O(nlogn)
;针对数字 a
、b
的遍历,是两次循环,时间复杂度为 O(n^2)
;求取数字 c
、d
过程中使用双指针,并且为满足不产生重复数据的要求,每次搜索次数小于数组规模,故时间复杂度为 O(n)
。综上所述,本算法时间复杂度为 O(n^3)
。
AC 样例
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
const res = [];
nums = nums.sort((a, b) => a - b);
for(let a = 0; a < nums.length; a++) {
// 去重 a
if(a > 0 && nums[a] == nums[a-1]) continue;
for(let b = a + 1; b < nums.length; b++) {
// 去重 b
if(b > a + 1 && nums[b] == nums[b-1]) continue;
let d = nums.length - 1;
for(let c = b + 1; c < nums.length; c++) {
// 去重 c
if(c > b + 1 && nums[c] == nums[c-1]) continue;
while(d > c && nums[a] + nums[b] + nums[c] + nums[d] > target) d--;
if(d == c) break;
if(nums[a] + nums[b] + nums[c] + nums[d] == target) res.push([nums[a], nums[b], nums[c], nums[d]]);
}
}
}
return res;
};