关于leetcode:前端leetcde算法面试套路之双指针

前言

上一 part 刚写完二分和滑窗，他们都属于非凡的双指针办法，所以这一 part 间接汇总一下除了非凡的二分和滑窗外的其余双指针写法

这里次要是快慢指针和端点指针， 解决一些一次遍历搞不掂，多个指针协商干活不累的题目，基本上感觉属于一种解题上的思路，一次不行，我就两次的样子；

所以刷完根底双指针，而后滑窗和二分后，这种思路在今后解题上应该会不定期能冒出来吧；

所以下期学习另外一种解题思路，回溯吧；

注释

双指针在很多罕用的数据结构和算法中，都曾经用到，比方说链表遍历过程中，就能够用双指针找中位数，找环；在二分法中用到的也是双指针；滑动窗口，以及双滑动窗口等

所以双指针是一个解决问题的思路，当设置一个指针遍历不足以造成对照的时候，能够设置更多的参照指针来服务本人，只是个别状况两个指针足以，所以这种解决思路称为双指针

快慢指针

比拟常见的双指针模式，个别是快指针走 2 步，慢指针走 1 步，达到一种对照的作用；
解决了形如链表的中位数，链表有环 等问题；

还有一种是读写指针，这种也是一个指针 read 先走，而后触发某个条件之后，才会让 write 走，也就造成了快慢的成果；

左右端点指针

最常见的就是二分法，都是设置 l r 指针，而后向两头合拢；所以所有的二分法的应用也是双指针的应用

还有一种就是排好序之后，依据最大值和最小值之间的运算来求值的，这个时候也须要端点指针

找反复值的时候，转换成链表找环 -- 快慢指针的变形

在做快慢指针的题目的时候，咋一看题目和快慢指针没有一毛线关系，然而个别都是迭代啊，或者反复值啊什么的，反正就是须要进行雷同的运算,须要判断是否已经呈现过雷同的值, 这个时候，要不就用 hashMap 缓存一波，要不就用快慢指针，将原题转成类型链表的构造，next 指针就是对应的迭代函数，而后求是否有环(202. 高兴数), 或者求环的入口地位（287. 寻找反复数）

当然下面这种属于非凡题目的非凡做法，比方说 287. 寻找反复数 那是因为这里的下标和值刚好没法齐全重合，且有反复数，要是值也是从 [0,n-1]，那就没法子用值当下标的写法了

题目汇总

快慢指针

• 142. 环形链表 II
• 287. 寻找反复数
• 80. 删除有序数组中的反复项 II
• 202. 高兴数

左右端点指针

• 16. 最靠近的三数之和
• 713. 乘积小于K的子数组
• 977. 有序数组的平方
• 875. 爱吃香蕉的珂珂
• 881. 救生艇

二分法（这里只有链接，具体能够去看二分的题）

模板1

• 704. 二分查找
• 69. x 的平方根
• 374. 猜数字大小
• 441. 排列硬币
• 33. 搜寻旋转排序数组 模板2
• 278. 第一个谬误的版本
• 162. 寻找峰值
• 153. 寻找旋转排序数组中的最小值
• 154. 寻找旋转排序数组中的最小值 II 模板3
• 在排序数组中查找元素的第一个和最初一个地位
• 找到 K 个最靠近的元素 其余
• 50. Pow(x, n)
• 367. 无效的齐全平方数
• 744. 寻找比指标字母大的最小字母
• 349. 两个数组的交加
• 350. 两个数组的交加 II
• 167. 两数之和 II - 输出有序数组
• 287. 寻找反复数
• 4.寻找两个正序数组的中位数
• 410. 宰割数组的最大值

滑动窗口（也是属于双指针，感觉匹配快慢指针一点）

• 438. 找到字符串中所有字母异位词
• 3. 无反复字符的最长子串
• 76. 最小笼罩子串
• 209. 长度最小的子数组
• 904.水果成篮
• 930. 和雷同的二元子数组
• 992. K 个不同整数的子数组
• 978. 最长湍流子数组
• 1004. 最大间断1的个数 III
• 1234. 替换子串失去均衡字符串
• 1248. 统计「柔美子数组」
• 1658. 将 x 减到 0 的最小操作数

参考视频：传送门

题目

142. 环形链表 II

剖析

1. 典型的快慢指针写法，在链表专题写过相应的题解了
2. 142. 环形链表 II
3. 做一下这个题，是为了下一题的前置

var detectCycle = function(head) {    const emptyNode = new ListNode()    emptyNode.next = head;    if(!head) return null    let slow  = fast = emptyNode    while(fast && fast.next){        slow = slow.next        fast = fast.next.next        if(slow === fast){            // 相交了，证实相交了            let next = emptyNode            while(next!== slow){                next = next.next                slow = slow.next            }            // 相交的时候，就是环入口            return slow        }    }    return null}

287. 寻找反复数

剖析 -- 双指针法（快慢指针）

1. 审题: 只有一个反复的整数，而这个反复的整数的呈现次数不确定
2. 能够用 map 用空间换工夫，也能够排序之后间接找，然而这样都不合乎题意
3. 之前在二分法 tab 中做了一次: 287. 寻找反复数
4. 这道题是能够用快慢指针做的，就是将数组中的值当成是指向数组下标的指针，而后将整个数组转成链表；而题目就转成了，始终一个环形链表（有反复的值，也就是在链表中有反复指向的指针），求环的入口；
5. 参考寻找环形链表的入口 -- 142. 环形链表 II
6. 工夫复杂度 O(N)

var findDuplicate = function (nums) {    let slow = fast = 0 // 初始节点    while(fast && nums[fast]){        slow = nums[slow]        fast = nums[nums[fast]]        if(slow === fast){            let next = 0            while(next !== slow) {                slow = nums[slow]                next = nums[next]            }            return slow        }    }}

剖析

1. 给定长度为 n+1 的 nums，外面的值都是 1-n, 本题中只有一个值是反复的，找出这个值
2. 留神这里只是表明反复的只有一个值，然而这个值反复多少次并没有阐明，所以不能用简略的异或二进制解决
3. 然而咱们能够选定以 mid 值，而后判断小于等于 mid 值 count，如果 count 超出了 mid ，证实在 [1,mid] 中至多有一个值反复了，这个时候能够砍掉右侧局部
4. 当 left 和 right 相等之后，即找到了惟一反复的值，因为这个时候左右两侧的值都不服要求，就只有这个了
5. 工夫复杂度 O(nlohn), 空间复杂度 1

var findDuplicate = function (nums) {  let left = 1,    right = nums.length - 1; // 值是 1 - n    while (left < right) {    const mid = ((right - left) >> 1) + left;    const count = nums.reduce((prev, cur) => (cur <= mid ? prev + 1 : prev), 0); // 小于等于 count 的值    if (count > mid) {      // 如果 [1,mid] 这个数组满值的状况才只有 mid 个，当初 count 如果比这个还大，证实反复的值在这外面      right = mid;    } else {      left = mid + 1;    }  }  return left;};

80. 删除有序数组中的反复项 II

读写指针也算是快慢指针的一种，读指针个别会先走，触发某种条件之后，才会挪动写指针

剖析 -- 读写指针

1. 给定的数组是排好序的，而后须要删除多余节点，使得最多呈现 2次
2. 设置读写指针 read 和 write, 遍历的每一步中，读写指针都指向雷同的值，然而指向的下标可能不一样
3. 当雷同的值超过了2， 即 [left,right] 的长度超出 2， 则原地删除 right 指针指向的值
4. 工夫复杂度 O(n)

 var removeDuplicates = function(nums) {    let write = read = 0    while(read <nums.length){        while(nums[write] === nums[read] && read <nums.length ){            if(right-left+1 > 2){                nums.splice(read,1) //删除读指针以后的下标            } else{                read++            }        }        // 一轮雷同值走完，写指针和读指针指向同一个值        write = read    }};

202. 高兴数

剖析

1. 这里盲猜是用迭代的写法来求，因为没次按要求革新一个 ret，如果不合乎胜利或者失败要求，就会持续迭代上来
2. 因为是一直按十进制位取平方求和，所以截止条件应该是符合要求，失去的和 sum === 1
3. 如果不符合条件，必定就是遭逢到循环了，这里用 set 缓存所有迭代过程中的 ret，只有迭代过程中再次出现 set 中的值，就是导致循环了，间接返回false 即可
4. 工夫复杂度,这个不太会求，然而会须要 set 来缓存数据

var isHappy = function (n) {    const set = new Set()    let result    const dfs = n => {        let ret = 0;        while (n) {          ret += Math.pow(n % 10, 2);          n = Math.floor(n / 10);        }        if(ret === 1)  {            result = true            return         }        if(set.has(ret)){            result = false            return         }        set.add(ret)        // 迭代写法，如果用 return 就是递归的写法了        dfs(ret);    }    dfs(n)    return result};

剖析

1. 这是快慢指针专题，所以其实能够用快慢指针是否有环来解决
2. 所以迭代的过程就和链表的 next 是差不多的，如果呈现环，则返回 false，如果呈现值 1，则返回 true
3. 这样就不须要额定的 set 去缓存值了

var isHappy = function (n) {    function getNext(n) {        let ret = 0;        while (n) {          ret += Math.pow(n % 10, 2);          n = Math.floor(n / 10);        }        return ret    }    let s = f = n // 初始化的值都是 n    while(f !== 1 && getNext(f) !== 1){        s = getNext(s)        f = getNext(getNext(f))        if(s === f) return false    }    return true}

16. 最靠近的三数之和

剖析

1. 暴力解法，间接固定左右两个节点i,j，而后设置第三个指针 k 在两个指针之间遍历求和，找出最靠近 target 的值
2. i 遍历一次nums，j 和 k 每固定一次加起来遍历一次 nums，所以工夫复杂度为 O(n2)

var threeSumClosest = function(nums, target) {    const len = nums.length     let ret;    let temp = Infinity // sum 与 target 的相差值    for(let i =0;i<len-2;i++){        for(let j = len-1;j>1;j--){            for(let k = i+1;k<j;k++){                const sum=nums[i]+nums[j]+nums[k]                const bet = Math.abs(sum-target)                 if(bet<temp){                    // 这一组的和比之前的更靠近 target                     ret = sum;                    temp = bet                }            }        }    }    return ret}; 

713. 乘积小于K的子数组

剖析

1. 求的是符合要求的，间断的子数组的最大个数，盲猜能够用不定大小的滑窗解决
2. 挪动 r 指针扩大窗口，而后当乘积超出 k 的时候，开始膨胀 l 指针，最初失去一个符合要求的窗口 [l,r]
3. 在这个窗口 [l,r] 中，任意的一种组合都符合要求，因为组合属于一种个性的判断，所以不须要用双窗口来求符合要求的数量，间接 r-l+1 即可
4. 须要留神的时候，膨胀 l 指针的时候，断定条件 l<=r 的起因是，以后 nums[r] 可能就比 k 大，这个状况应该膨胀窗口为 0，并走到下一步
5. 工夫复杂度 O(n)

 var numSubarrayProductLessThanK = function (nums, k) {    let l = (r = 0);    let product = 1; // 默认最小为 1    let ret = 0; // 最大长度    while (r < nums.length) {      const rr = nums[r];      product *= rr;      while (product >= k && l <= r) {        // 超出了 k        ll = nums[l];        product = product / ll;        l++;      }      // 这个时候 [l,r] 之间的值的乘积是小于 k 的      ret += r - l + 1;      r++;    }    return ret;  };

977. 有序数组的平方

剖析

1. 散发左右指针l,r, 而后用一个额定的数组来存储平方后的数组即可
2. 因为这是一个排好序的增序列，会存在正数，然而值的平方最大值就在数组的两侧，所以每次比拟两侧的值，就能获取到相应的最大值，而后 unshift 到数组中即可
3. 工夫复杂度 O(n), 空间复杂度 O(n)

var sortedSquares = function(nums) {    let l = 0,r = nums.length- 1    let ret = []    while(l<=r){        if(nums[r]>Math.abs(nums[l])){            ret.unshift(Math.pow(nums[r],2))            r--        }else{            ret.unshift(Math.pow(nums[l],2))            l++        }    }    return ret};

875. 爱吃香蕉的珂珂

剖析 -- 二分

1. l = 1 , r = piles[max],他们别离代表了最大和最小的速度； 这样找出两头值，而后判断是否能在 h 小时内吃完，能吃完则向左迫近，不能吃完则向右迫近，直到最小的速度呈现
2. 每一次二分取 mid 之后，都要遍历一次 piles， 所以工夫复杂度是 nlogn

var minEatingSpeed = function (piles, h) {  let l = 1,    r = piles.reduce((prev, cur) => (prev >= cur ? prev : cur), 1);  while (l <= r) {    const mid = ((r - l) >> 1) + l;    if (getHours(mid) > h) {      // 须要的工夫超出了 h, 证实速度不够      l = mid + 1;    } else {      r = mid - 1;    }  }  // 速度为 v 的时候，须要多久吃完  function getHours(v) {    let ret = 0;    for (let i = 0; i < piles.length; i++) {      ret += Math.ceil(piles[i] / v);    }    return ret;  }  return l;};

881. 救生艇

剖析

1. 因为这里最多只能载人 2， 负重最多是 limit，所以抉择载人的时候，尽量先抉择最重的和最轻的进行匹配，尽量一船二人坐，能够缩小数量，所以先给 people 排序
2. l,r 指针指向最轻和最重的人
3. 而后每次求出2人组合的最轻总量和 sum， 让它和 limit 进行比拟，进而管制 l, r 的挪动
4. 工夫复杂度 O(nlogn) 次要是排序问题

var numRescueBoats = function (people, limit) {  let l = 0,    r = people.length - 1;  people.sort((a, b) => a - b);  let count = 0; // 须要的船的数量  while (l <= r) {    const sum = people[l] + people[r];    if (sum > limit) {      r--;    } else {      l++;      r--;    }    count++;  }  return count;};