# 前言
最近准备好好开始刷 leetcode 了,而刷题之余写一些总结性质的东西我也觉得是非常有必要的。
最近刚好在回顾题目的时候看到了二数之和、三数之和、四数之和等等的题目,并且它们的解决方式都十分的类似,因此想着趁这个机会进行一些总结。
当然之后也会总结一些其他性质的题目,这次写文当作是一个开端吧,我希望我的算法水平能在日积月累中取得一些成效~~
# 二数之和
这道题目在 leetcode 上是排名 No.1,可见是无数入门算法的同学们的初见,对其感情之深(T v T)当然刚刚开始我也一头雾水没啥思路。
我觉得对于算法题而言,最重要的就是看到这个题目之后你要有思路怎么去解决。无论是数据结构、还是采用什么算法,都需要脑海里面蹦出来有一个解决这个问题的想法然后再付诸行动。 当然这个思路也是刷题刷出来的。
# 题目
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums [0] + nums [1] = 2 + 7 = 9
所以返回 [0, 1]。
# 解答
我们首先看这个题目,其实很简单,就是从一个数组中找到一个组合,让这个组合中的值和为 target。
那么很简单啊,直接来个循环遍历不就可以了?外一层里一层 for 循环不断相加,判断和是否为 target 即可。
当然这样是没问题!你可以很顺畅的写出来,但是这样子放在 leetcode 上面是通不过的,因为这个两数的时间复杂度就达到 了,leetcode 上面的测试用例后面还涉及到巨量的数据,这怎么跑得通呢?
况且后面还有三、四、五数之和,两数的就得 ,三数的岂不是得 ?
先讲个结论:遇到这种你的第一直觉是循环遍历解决的问题,核心思路应该是怎么降低遍历次数。
对于这种 n 数之和的问题而言,是可以将原本的循环次数给降低一个维度的。
我们先来看看正常的 1 维循环写法(2 维的太过于无脑,在这里不写了):
function twoSum1(nums: number[], target: number): number[] { | |
// 1 维循环算法 | |
// 1. 将 nums 从小到大排列 | |
nums.sort((a, b) => a - b); | |
// 2. 定义变量 | |
const length: number = nums.length; | |
let end: number = length - 1; | |
const resArr: number[] = []; | |
// 3. 遍历数组 | |
for (let i = 0; i < length; i++) { | |
if (i > 0 && nums[i] === nums[i - 1]) { | |
continue; | |
} | |
while (nums[i] + nums[end] > target) { | |
end--; | |
} | |
if (nums[i] + nums[end] === target) { | |
resArr.push(i, end); | |
break; | |
} | |
} | |
return resArr; | |
} |
首先调用数组的 sort
方法,将 nums
数组从小到大排序。
然后定义了三个变量: length
用于存储 nums
数组的长度; end
初始化为 nums
数组的最后一个元素的索引; resArr
是一个空数组,用于存储结果。
接下来,函数使用一个 for
循环遍历 nums
数组。在每次循环中,首先检查当前元素是否与前一个元素相同,如果相同,则跳过当前循环,进入下一次循环。因为在排序后的数组中,相同的元素会被放在一起,如果当前元素与前一个元素相同,那么它们的和肯定已经被计算过了。
然后使用一个 while
循环,不断地将 end
减 1,直到 nums[i] + nums[end]
的值不大于 target
。这是因为 nums
数组已经被排序,所以如果 nums[i] + nums[end]
的值大于 target
,那么只能通过减小 end
来减小它们的和。
最后,如果 nums[i] + nums[end]
的值等于 target
,那么就将 i
和 end
添加到 resArr
数组中,并跳出 for
循环。
函数最后返回 resArr
数组,即包含两个和为 target
的元素的索引的数组。
这个就是 n 数之和的模板套路写法! 梳理一下整个解题的步骤:
- 首先对传进来的数组进行从小到大的排序,便于之后的遍历。因为已知整个数组是从小到大的,我们可以从小开始遍历,然后取最大的开始进行相加,最后逐层的进行拟合。
- 然后定义变量,主要的变量有:
- 数组长度 length
- 指针。这个指针按照是 n 数循环的问题,定义 n-1 个即可。
- 存储结果的数组 resArr。
- 对整个 nums 数组进行最外层循环,遇到 nums [i] 和 nums [i-1] 相等的,直接跳过即可。
- 在每一次的循环内部,遵循一个规律:只根据拟合结果同时改变最后两个指针的值,前面的 n-3 个指针全部都是根据 for 循环自身来改变。也就是说,这样子可以把原本的全部 for 循环给降低一层维度。
是不是还是有点云里雾里的?可以看一下三数之和的写法。
在这里我再附加一个对于特定的二数之和问题的哈希表写法 —— 借助 Map 的 get、set 方法来实现对于 target - nums [i] 的查找。
这个 Map 的 key 是这个 nums 数组中的数据值,value 是这个数据对应的 nums 数组的下标。这样子只要 get 对应的 value,就可以直接拿到其对应的下标了。
所以我们只用一次遍历,然后直接使用 get 看看能不能拿得到 target-nums [i] 的下标,能拿到就代表找到了。在这里也给出对应的算法代码:
function twoSum(nums: number[], target: number): number[] {// 1. 生成一个 ma p,key 为 nums 的值,value 为 nums 的下标
let helperMap: Map<number, number> = new Map();// 2. 定义一个变量,用来存储 map 中是否存在 target - nums [i] 的值
let index: number | undefined;// 3. 定义结果数组
let resArr: number[] = []; for (let i = 0; i < nums.length; i++) { index = helperMap.get(target - nums[i]); if (index !== undefined) { resArr = [i, index];}
helperMap.set(nums[i], i);}
return resArr;}
# 三数之和
# 题目
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [[-1, 0, 1], [-1, -1, 2] ]
# 解答
可以看到,三数之和要求我们返回的是全部的符合条件的三元组集合,返回形式是矩阵的形式。因此我们就必须得进行遍历,不然是根本找不出所有的组合。
我们可以按照上述方法如法炮制:
function threeSum(nums: number[]): number[][] { | |
// 1. 对原数组进行排序 (从小到大),便于之后遍历 | |
nums.sort((a, b) => a - b); | |
// 2. 定义变量:数组长度,左指针,右指针,结果数组 | |
let length = nums.length; | |
let left: number = 0; // 最左端 | |
let right: number = length - 1; // 最右端 | |
let resArr: number[][] = []; // 存放结果的数组 | |
// 3. 遍历数组 | |
for (let i = 0; i < length; i++) { | |
// 特殊情况(两种): | |
// 3.1 nums 经过排序后,只要 nums [i]>0, 此后的 nums [i] + nums [left] + nums [right] 均大于 0, 可以提前终止循环。 | |
if (nums[i] > 0) { | |
return resArr; | |
} | |
// 3.2 如果当前值与前一个值相同,则跳过 | |
if (i > 0 && nums[i] === nums[i - 1]) { | |
continue; | |
} | |
// 3.3 更改左指针和右指针的值,缩小范围 | |
left = i + 1; | |
right = length - 1; | |
while (left < right) { | |
// 3.4 如果三数之和等于 0,则将结果添加到结果数组中 | |
let total: number = nums[i] + nums[left] + nums[right]; | |
if (total === 0) { | |
resArr.push([nums[i], nums[left], nums[right]]); | |
left++; | |
right--; | |
// 如果左 / 右指针的值与前 / 后一个值相同,则跳过 | |
while (nums[right] === nums[right + 1]) { | |
right--; | |
} | |
while (nums[left] === nums[left - 1]) { | |
left++; | |
} | |
} else if (total < 0) { | |
left++; | |
} else { | |
right--; | |
} | |
} | |
} | |
return resArr; | |
} |
可以看到,是非常公式化的模板,唯一需要注意的就是 3.3 步开始的 while 循环判断。需要对 left < right 进行判断,因为 left 和 right 都是同时的进行右移 / 左移的。直到它们俩相遇,这一层的遍历才算是结束,开启下一个循环的遍历。
# 四数之和、五数之和、...
按照上述方法,我们其实也就很简单的可以写出四、五、n 数之和的公式化写法。在这里给出四数之和的写法:
function fourSum(nums: number[], target: number): number[][] { | |
// 1. 对原数组进行排序 | |
nums.sort((a, b) => a - b); | |
// 2. 定义变量:数组长度,第一个指针,第二个指针,第三个指针,第四个指针,结果数组 | |
let first: number = 0, | |
second: number, | |
third: number, | |
fourth: number; | |
let length: number = nums.length; | |
let resArr: number[][] = []; | |
// 3. 遍历数组 | |
for (; first < length; first++) { | |
// 3.1 如果当前值与前一个值相同,则跳过 | |
if (first > 0 && nums[first] === nums[first - 1]) { | |
continue; | |
} | |
// 3.2 更改第二个指针的值,缩小范围,并基于第二个指针遍历数组 | |
for (second = first + 1; second < length; second++) { | |
// 也是跳过重复的值 | |
if (second - first > 1 && nums[second] === nums[second - 1]) { | |
continue; | |
} | |
third = second + 1; | |
fourth = length - 1; | |
while (third < fourth) { | |
let total: number = | |
nums[first] + nums[second] + nums[third] + nums[fourth]; | |
if (total === target) { | |
resArr.push([nums[first], nums[second], nums[third], nums[fourth]]); | |
third++; | |
fourth--; | |
while (nums[third] === nums[third - 1]) third++; | |
while (nums[fourth] === nums[fourth + 1]) fourth--; | |
} else if (total < target) { | |
third++; | |
} else { | |
fourth--; | |
} | |
} | |
} | |
} | |
return resArr; | |
} |
可见基本的模板都是相同的。
# 总结
n 数之和的套路十分单纯: 减少循环的嵌套层数 。虽然对于最后的 n 数问题,最理想的全遍历减少嵌套次数只能是一层,不过也是目前效率最高的一种解法。
由于我本人几乎没什么机会接触一些真正的算法相关知识,所以我只能在这个小博客进行一些比较粗浅的经验记录~如果有不合理的地方,希望浏览到这个文章的大家能够多多留言哈哈!
之后打算理一理链表相关的问题。