前端算法系列之 双指针
前言
最近在系统的学习算法知识,以锻炼自己的逻辑分析能力和将想法变为代码的能力;为了给自己学习的反馈、和对自己成果的验收,决定写这个系列,输出和学习本身相辅相成,望与大家共同成长。
另外,我喜欢用最简洁的表达来阐述观点,所以,看我的文章,不要漏字~
双指针
先说结论,我们用增加一个指针的方式,来降低算法所用的时间或空间。
举个例子
看如下题目:给定一个有序数字数组和一个目标和,在数组中找到一对和等于给定目标的数组。
先看最笨的方式,暴力~,大家都能想到,但是不好意思在面试官面前动手写的方式:第一层遍历,取出一个值x,第二层遍历,找到和x的和为目标值的值y,记录并输出。
痛点:我们遍历了两次。
想起我们的结论了吗,我们要用增加一个指针的方式,降低时间复杂度。
通常大家在看题目答案的时候,有一个困惑,就是我知道这样做真的有效,但是具体的办法究竟是怎么想出来的呢?不急,我们慢慢看
那好,我们现在有两个指针了,我们最终的目的,就是将两个指针通过某种方式,移动到我们的答案上,那么思路呼之欲出,我们将两个指针分别放在头部和尾部,先计算他们的和,如果和大了,就让他小一点,那么怎么小一点呢,将尾部的指针往后移(有序数组哦),反之和小了,头部指针忘后移动,这样下去,我们总能将和调整到目标和,如果没有?那首尾指针相遇的时候,就停止遍历,代码如下。
function pair_with_target_sum(arr, targetSum) {
let left = 0;
let right = arr.length - 1;
while (arr[left] + arr[right] !== targetSum) {
if (arr[left] + arr[right] > targetSum) {
right—
} else {
left++
}
if (right <= left) {
return [-1, -1]
}
}
return [left, right]
}
思考题:如果我们将题目改为找到数组中三个元素,和一个目标和,你能搞定吗?你还能通过增加一个指针的方式来降低暴力法所需要的遍历层数吗?
另外,作为新手,我们思考解题方法时不必要直接想出结果,不妨先理清暴力法的逻辑,然后再增加指针,优化暴力法,对于新手来说,慢就是快。
再来一个例子
当然,走到这里你会知道,这个例子要去节省空间复杂度。不过不怕你知道,试一试吧。
给定一个已排序数字数组,删除其中所有重复的数字。 要求不使用任何额外的空间; 在删除就地重复项之后,返回数组的新长度。
现在你可以自己思考一下,尝试一下,要是5分钟还没思路,就回来看答案吧~
同样,两个指针,一个跑的快,在前边做“探查”;另一个在后边做记录,因为数组已经排序,每当探查到一个值 X,如果 记录索引 的下一位不是X,就说明这个值没有被记录过,这是我们将 记录索引 的下一位替换为X,最后数组的长度,就是记录索引 + 1。
代码如下:
function remove_duplicates(arr) {
let recorder = 0;
for(let explorer = 1; explorer < arr.length; explorer++) {
if(arr[explorer] !== arr[recorder]) {
arr[recorder + 1] = arr[explorer]
recorder++
}
}
return recorder + 1;
}
以上