• home > theory > algorithm > leetcode >

    双指针:对撞/快慢/分离/滑动窗口的案例(数组/回文/求和等)

    Author:zhoulujun Date:

    双指针的种类有对撞指针(Collision)、快慢指针(Forward)、分离双指针(Parallel)、滑动窗口(Sliding Window)等,分别对应什么场景和leetcode如何解题呢?

    回顾《数组二分查找到二分法的感悟笔记》,其实二分查找就是双指针。对于双指针,特别推荐:


    双指针的种类

    双指针种类

    对撞指针(Collision)

    指的是两个指针left、right 分别指向序列第一个元素和最后一个元素,然后left 指针不断递增,right 不断递减,直到两个指针的值相撞(即left==right),或者满足其他要求的特殊条件为止。

    对撞指针

    适用场景

    对撞指针一般用来解决有序数组或者字符串问题:

    • 查找有序数组中满足某些约束条件的一组元素问题:比如二分查找、数字之和等问题。

    • 字符串反转问题:反转字符串、回文数、颠倒二进制等问题。

    快慢指针(Forward)

    两个指针方向相同。适合解决数组中的移动、删除元素问题,或者链表中的判断是否有环、长度问题。

    快慢指针

    1. 使用两个指针slow、fast。slow 一般指向序列第一个元素,即:slow=0,fast 一般指向序列第二个元素,即:fast=1。

    2. 在循环体中将左右指针向右移动。当满足一定条件时,将慢指针右移,即slow+=1。当满足另外一定条件时(也可能不需要满足条件),将快指针右移,即fast+=1。

    3. 到快指针移动到数组尾端(即fast==len(nums)−1),或者两指针相交,或者满足其他特殊条件时跳出循环体。

    适用场景

    • 解决链表中的问题,如检测链表中是否存在环、找到链表的中点等。

    • 解决数组中的问题,如移除数组中的重复元素等。


    分离双指针(Parallel)

    两个指针分别属于不同的数组,两个指针分别在两个数组中移动。

    分离双指针

    适用场景

    • 查找两个数组的交集:找到两个数组中共同包含的元素。

    • 查找两个数组的并集:找到两个数组中所有不同的元素。

    • 比较两个数组的差异:比较两个数组并找出它们的差异。



    滑动窗口(Sliding Window)

    滑动窗口通过维护一个窗口,从左到右移动窗口,以找到满足特定条件的子数组或子串。

    滑动窗口解题思路滑动窗口可获得的最大点数 Maximum Points You Can Obtain from Cards

    滑动窗口的思想非常简单,它将子数组(子字符串)理解成一个滑动的窗口,然后将这个窗口在数组上滑动,在窗口滑动的过程中,左边会出一个元素,右边会进一个元素,然后只需要计算当前窗口内的元素值即可

    算法思路

    1. 使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个「窗口」。

    2. 先不断地增加 right 指针扩大窗口 [left, right],直到窗口符合要求

    3. 停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求。同时,每次增加 left,我们都要更新一轮结果

    4. 重复第 2 和第 3 步,直到 right 到达尽头。

    第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解。 左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。

    适用场景

    滑动窗口算法思想是非常重要的一种思想,可以用来解决数组,字符串的子元素问题。它可以将嵌套循环的问题,转换为单层循环问题,降低时间复杂度,提高效率。

    • 适用于解决数组或字符串中子串问题,如找到最小覆盖子串、找到最长无重复字符子串、如找到数组中的最长连续子数组等。




    双指针的题包括

    1. 两数之和(Two Sum):在数组中找到两个数,使它们的和等于目标值。

    2. 三数之和(3Sum):在数组中找到所有不重复的三元组,使得三个数的和等于零。

    3. 四数之和(4Sum):在数组中找到四个数,使它们的和等于目标值。

    4. 两数之和 II - 输入有序数组(Two Sum II - Input array is sorted):在有序数组中找到两个数,使它们的和等于目标值。

    5. 盛最多水的容器(container-with-most-water):找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

    6. 移动零(Move Zeroes):给定一个数组,将数组中的零移到数组的末尾,同时保持非零元素的相对顺序。

    7. 反转字符串中的元音字母(Reverse Vowels of a String):给定一个字符串,反转字符串中的所有元音字母。

    8. 最长连续递增序列(Longest Continuous Increasing Subsequence):给定一个未排序的整数数组,找出最长连续递增序列的长度。

    9. 最长连续递减序列(Longest Continuous Decreasing Subsequence):给定一个未排序的整数数组,找出最长连续递减序列的长度。

    10. 合并区间(Merge Intervals):给定一个区间的集合,合并所有重叠的区间。

    11. 合并两个有序数组(Merge Sorted Array):给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

    12. 两个数组的交点(Intersection of Two Arrays):给定两个数组,编写一个函数来计算它们的交集。

    13. 两个数组的交点 II(Intersection of Two Arrays II):给定两个数组,编写一个函数来计算它们的交集,且结果可以是非递减顺序。

    14. 最小覆盖子串(Minimum Window Substring):给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。

    15. 最长重复子数组(Maximum Length of Repeated Subarray):给定两个整数数组 A 和 B,找到两个数组中公共的、长度最长的子数组的长度。

    16. 最长和谐子序列(Longest Harmonious Subsequence):给定一个整数数组,找出数组中最长的和谐子序列的长度。

    17. 有效的括号(Valid Parentheses):给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串,判断字符串是否有效。

    18. 合并K个排序链表(Merge k Sorted Lists):合并 k 个排序链表,返回合并后的排序链表。

    19. 删除排序数组中的重复项(Remove Duplicates from Sorted Array):给定一个排序数组,需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    大哥分类好的:

    https://algo.itcharge.cn/01.Array/04.Array-Two-Pointers/02.Array-Two-Pointers-List/

    https://github.com/labuladong/fucking-algorithm/blob/master/算法思维系列/双指针技巧.md


    对撞双指针

    太多了,下面挑一些典型案例来记:

    两数之和

    function test(nums,target){
      let left = 0,right = nums.length-1;
      while (left<right){
        const sum = nums[left]+nums[right];
        if(sum===target){
          return  [left,right]
        }if(sum>target){
          right--
        }else {
          left --
        }
      }
      return [-1,-1];
    }

    两数之和其实就是二分查找

    三数之和

    https://programmercarl.com/0015.三数之和.html

    这个解释:https://cloud.tencent.com/developer/article/2262666

    三数之和动图&代码

    function threeSum(arr, target) {
      if (arr.length < 3) return []; // 如果数组长度小于3,直接返回空数组
      arr.sort((a, b) => a - b); // 对数组进行排序
      const result = []; // 初始化结果数组
      // 遍历数组,使用双指针法寻找三数之和
      for (let i = 0; i < arr.length - 2; i++) {// 记得是 arr.length - 2
        if (i > 0 && arr[i] === arr[i - 1]) continue; // 跳过重复的元素,避免重复解
        /**
         *不可以改为:if (arr[i] === arr[i - 1])  i++;会导致在某些情况下跳过有效解。例如,对于数组 [0, 0, 0] 和目标值 0,
         正确的解应该是 [[0, 0, 0]],但使用 if (arr[i] === arr[i - 1]) i++ ; 会导致跳过所有的 0,从而得到空解。
        */
        let left = i + 1; // 初始化左指针
        let right = arr.length - 1; // 初始化右指针
    
        while (left< right) { // 当左指针小于右指针时,继续寻找三数之和
          const sum = arr[i] + arr[left] + arr[right]; // 计算当前三数之和
          if (sum === target) { // 如果三数之和等于目标值,将结果添加到结果数组中,并移动左右指针
            result.push([arr[i], arr[left], arr[right]]);
            left++;
            right--;
    
            // 跳过重复的元素,避免重复解
            while (left< right && arr[left] === arr[left + 1]) left++;
            while (left< right && arr[right] === arr[right - 1]) right--;
          } else if (sum< target) {// 如果三数之和小于目标值,移动左指针
            left++;
          }else {// 如果三数之和大于目标值,移动右指针
            right--;
          }
        }
      }
    
      return result; // 返回结果数组
    }


    四数之和

    https://leetcode.cn/problems/4sum/description/

    var fourSum = function (nums, target) {
      const length = nums.length;
      if (length < 4) {
        return [];
      }
      const result = [];
      // 首先排序,然后
      nums.sort((a, b) => a - b);
      for (let i = 0; i < length - 3; i++) {// 外层循环,遍历数组中的每个元素
        if (i > 0 && nums[i - 1] === nums[i]) {// 跳过重复的元素
          continue;
        }
        // 因为升序,如果前四个就大于target,再往后取只会更大,直接跳出循环
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
          break;
        }
        //num[i] 和最大3个数相加都小与target,那么和其他数相加只会更下,所以只有加大当前值(前移)
        if (nums[i] + nums[length - 1] + nums[length - 2] + nums[length - 3] < target) {
          continue; //前元素 nums[i]与数组中最大的3个数(最后三个数)相加还是小于target,则num[i]不可能找到一个和为 target 的四元组。
        }
        for (let j = i + 1; j < nums.length - 2; j++) {// 内层循环,遍历数组中的每个元素
          if (j > i + 1 && nums[j] === nums[j - 1]) {
            continue;
          }
          let left = j + 1, right = nums.length - 1;// 初始化左右指针
          while (left < right) {
            const sum = nums[i] + nums[j] + nums[left] + nums[right];
            if (sum > target) { // 如果和大于目标值,将右指针向左移动
              right--;
            } else if (sum < target) {
              left++;
            } else {
              result.push([nums[i], nums[j], nums[left], nums[right]]);
              while (left < right && nums[left] === nums[left + 1]) {// 跳过重复的元素
                left++;
              }
              left++;
              while (left < right && nums[right] === nums[right - 1]) {
                right--;
              }
              right--;
            }
    
          }
    
        }
      }
      return result;
    };

    解法是一样的。


    有序数组的平方

    https://leetcode.cn/problems/squares-of-a-sorted-array/

    给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

    示例 1:输入:nums = [-4,-1,0,3,10]   输出:[0,1,9,16,100]

    解释:平方后,数组变为 [16,1,0,9,100]   排序后,数组变为 [0,1,9,16,100]

    这个题有三种解法:

    1. 直接平方,然后再对结果排序。

    2. 利用类似归并排序算法,即依次比较原负数部分平方和正数部分平方使用两个指针分别指向位置 neg 和neg+1,每次比较两个指针对应的数,选择较小的那个放入答案并移动指针。当某一指针移至边界时,将另一指针还未遍历到的数依次放入答案。

    3. 双指针-直接比较、逆序放入(每次直接比较两个指针对应的数的平方值,选择较大的那个逆序放入答案并移动指针)

    推荐第三种方案,详细推荐阅读:https://programmercarl.com/0977.有序数组的平方.html


    function sortedSquares (nums) {
      // 因为数组是有序数组,如果数组全部为正数,直接返回即可。
      if(nums.length<2||num[0]>0){
        return nums.map(num=>num*num)
      }
      let l = nums.length;
      let result = new Array(l).fill(0);
      // 定义三个指针:i指向数组起始位置,j指向数组末尾位置,k指向结果数组末尾位置
      let leftKey = 0, rightKey = l - 1, resultRightKey = l - 1;
      // 使用双指针从数组两端向中间遍历
      while (leftKey <= rightKey) {
        let left = nums[leftKey] * nums[leftKey];
        let right = nums[rightKey] * nums[rightKey];
        // 比较左右指针对应的平方值,将较大的值放入结果数组的末尾
        if (left < right) {
          // 如果右指针的平方值较大,则将该值存入结果数组末尾,并将右指针向左移动
          result[resultRightKey--] = right;//先将 right 的值赋给 result[resultRightKey],然后再将其减1。
          rightKey--;
        } else {
          // 如果左指针的平方值较大或相等,则将该值存入结果数组末尾,并将左指针向右移动
          result[resultRightKey--] = left;
          leftKey++;
        }
      }
    
      // 返回最终的结果数组
      return result;
    };

    凡是有序的数组操作,都可以考虑下双指针:

    一个指针指向数组的开始,另一个指针指向数组的结束。

    比较两个指针所指向的元素的平方,将较大的平方放入结果数组的末尾,并将对应的指针向中间移动。

    重复步骤2,直到两个指针相遇。


    二维数组中的查找

    https://github.com/CyC2018/CS-Notes/blob/master/notes/4.%20二维数组中的查找.md

    给定一个二维数组,其每一行从左到右递增排序,从上到下也是递增排序。给定一个数,判断这个数是否在该二维数组中。

    Consider the following matrix:

    [

      [1,   4,  7, 11, 15],

      [2,   5,  8, 12, 19],

      [3,   6,  9, 16, 22],

      [10, 13, 14, 17, 24],

      [18, 21, 23, 26, 30]

    ]


    Given target = 5, return true.      Given target = 20, return false.

    要求时间复杂度 O(M + N),空间复杂度 O(1)。其中 M 为行数,N 为 列数。

    这个问题可以使用一种类似于双指针的方法解决,具体步骤如下:

    1. 从矩阵的右上角开始,即第一行的最后一个元素。

    2. 如果当前元素等于目标值,则返回 true。

    3. 如果当前元素大于目标值,则可以排除当前元素所在的列,将列索引向左移动。

    4. 如果当前元素小于目标值,则可以排除当前元素所在的行,将行索引向下移动。

    5. 重复步骤 2-4,直到找到目标值或者行索引或列索引超出矩阵范围。

    这种方法的时间复杂度为 O(M + N),其中 M 是行数,N 是列数,因为每次移动都可以排除一行或一列。


    二维数组中的查找

    function find(target, matrix) {
        let rows = matrix.length;
        let cols = matrix[0].length;
        let r = 0;
        let c = cols - 1; // 从右上角开始
    
        while (r <= rows - 1 && c >= 0) {
            if (target === matrix[r][c]) {
                return true;
            } else if (target > matrix[r][c]) {//如果 target 大于 matrix[r][c],则向下移动 r。
                r++;
            } else {//如果 target 小于 matrix[r][c],则向左移动 c。
                c--;
            }
        }
        
        return false;
    }


    快慢指针

    移除数组中的指定元素

    https://leetcode.cn/problems/remove-element/description/

    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

    示例 1:输入:nums = [3,2,2,3], val = 3               输出:2, nums = [2,2,_,_]

    示例 2:输入:nums = [0,1,2,2,3,0,4,2], val = 2    输出:5, nums = [0,1,4,0,3,_,_,_]

    解释: https://programmercarl.com/0027.移除元素.html

    function removeElement(nums, val) {
      let slow = 0,fast = 0,result = []
      while (fast<nums.length){//跑得快的那个先去寻找共同目标
        if(nums[fast] != val){
          result[slow++] = nums[fast]; //如果找到了,就送给跑得慢的那个
        }
        fast++;//但是不管是否找得到,跑得快的那方都一直奔跑到生命的尽头
      }
      return [slow,result];
    };

    27.移除元素-双指针法

    删除有序数组中的重复项

    https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

    给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

    示例 1:输入:nums = [1,1,2]                         输出:2, nums = [1,2,_]

    示例 2:输入:nums = [0,0,1,1,1,2,2,3,3,4]      输出:5, nums = [0,1,2,3,4]

    请留意题目中的:非严格递增排列 

    function removeDuplicates (nums) {
        let fast = 1, slow = 1;
        while (fast < nums.length) {
            if (nums[fast] !== nums[fast - 1]) {
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        return slow;
    };


    分离双指针

    两个数组的交集

    https://leetcode.cn/problems/intersection-of-two-arrays/description/

    给定两个数组 nums1 和 nums2 ,返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

    示例 1:输入:nums1 = [1,2,2,1], nums2 = [2,2]

    输出:[2]

    示例 2:输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]

    输出:[9,4]  备注: [4,9] 也是可通过的

    这是用hash做校验肯定是最快的O(mn),但是我们也可以用排序 + 双指针来做(O(m㏒m+n㏒n))。

    排序+分离双指针动态图

    function getIntersection(nums1, nums2) {
      // 首先,对两个输入数组进行排序。排序是为了确保我们可以方便地比较两个数组中的元素。
      nums1.sort((x, y) => x - y);
      nums2.sort((x, y) => x - y);
      
      const length1 = nums1.length, length2 = nums2.length;
      // 使用两个指针分别指向两个数组的开头,然后逐步向后移动,根据元素大小关系决定哪个指针向前移动。
      let index1 = 0, index2 = 0;
      const intersection = [];
      while (index1 < length1 && index2 < length2) {
        const num1 = nums1[index1], num2 = nums2[index2];
        if (num1 === num2) { // 说明找到了一个交集元素,将该元素添加到结果集,并同时递增 index1 、index2 
          // 保证加入元素的唯一性
          if (!intersection.length || num1 !== intersection[intersection.length - 1]) {
            intersection.push(num1);
          }
          index1++;
          index2++;
        } else if (num1 < num2) {//因为我们希望找到更大的元素。所以当num1 < num2,递增index1
          index1++;
        } else {
          index2++;
        }
      }
      return intersection;
    }


    滑动窗口

    滑动窗口和快慢指针都是在解决数组(或字符串)相关问题时常用的技巧,但它们的应用方式和解决问题的思路有一些不同。

    1. 滑动窗口(Sliding Window):

      • 定义:滑动窗口是指通过维护一个窗口(一般是数组或字符串的子区间),在这个窗口上通过移动左右边界来求解问题

      • 应用场景:通常用来解决需要找出数组或字符串中某种子串的最小值、最大值、符合条件的长度最短或最长等问题。

      • 特点:滑动窗口的核心思想是利用双指针或者队列,通过滑动窗口的左右边界来扩展或收缩窗口,从而在窗口内查找符合条件的解。

    2. 快慢指针(Two Pointers - Fast and Slow):

      • 定义:快慢指针是指在解决链表或数组中某些问题时,使用两个指针以不同的步长移动,从而解决问题的一种方法

      • 应用场景:主要用来解决链表中的环路检测、寻找中间节点、判断链表是否相交等问题。

      • 特点:快慢指针一般是在单链表中使用,快指针每次移动两步,慢指针每次移动一步,通过这种方式可以判断是否存在环路,或者找到链表的中间节点等。

    区别:

    • 问题类型:

      • 滑动窗口主要用于数组或字符串相关问题

      • 快慢指针更多地应用于链表相关问题

    • 移动方式:

      • 滑动窗口通过移动窗口的左右边界来扩展或收缩窗口,

      • 快慢指针则通过两个指针以不同的速度遍历链表来解决问题

    • 解决问题的思路:

      • 滑动窗口通常用于解决子数组或子字符串相关的问题

      • 快慢指针则更适合解决链表中的指针遍历问题。

    滑动窗口的题目:

    1. 无重复字符的最长子串(3)

    2. 滑动窗口最大值(239)

    3. 字符串相乘(43)

    4. 最小覆盖子串(76)

    5. 替换后的最长重复字符(424)

    6. 滑动窗口中位数(480)

    7. 字符串排列(567)

    8. 最长连续递增序列(674)

    9. 最长重复子数组(718)

    10. 无重复字符的最长子序列(1044)

    11. 可获得的最大点数(1432)

    别人总结好的:


    可获得的最大点数

    https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/description/

    几张卡牌 排成一行,每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给每次行动,你可以从行的开头或者末尾拿一张卡牌,最终你必须正好拿 k 张卡牌。你的点数就是你拿到手中的所有卡牌的点数之和。给你一个整数数组 cardPoints 和整数 k,请你返回可以获得的最大点数。

    示例 1:输入:cardPoints = [1,2,3,4,5,6,1], k = 3  输出:12

    示例 2:输入:cardPoints = [2,2,2], k = 2            输出:4

    不管怎么取,都是取头尾。比如我们可以假设一开始就是最左边的k个数字的和最大,之后滑动窗口,让窗口不停左滑动(每次滑动一个数字),并比较当前k个数字的和与上次的和谁更大。

    直接暴力解法:

    function maxScore(nums, k) {
      // 因为不管怎么样,都是从首尾开始取,那么就是掐头去尾
      let sum = 0;
    
      const n = nums.length;
      let selectFirst = k;
      while (selectFirst >= 0) {
        let temp = 0;
        for (let i = 0; i < selectFirst; i++) {//首先取头部的k个,然后尝试头头部取的个数从尾部不足
          temp += nums[i];
        }
        let selectLast = k - selectFirst;
        while (selectLast > 0) {
          temp += nums[n - selectLast];
          selectLast--;
        }
        sum = Math.max(sum, temp);
        selectFirst--;
      }
      return sum;
    }
    
    let cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3;
    console.log(maxScore(cardPoints, 3));

    这样写,学滑动窗口还干啥子?

    var maxScore = function (cardPoints, k) {
      let windowSum = 0;
      for (let i = 0; i < k; i++) {
        windowSum += cardPoints[i];
      };
      let n = cardPoints.length - 1;
      // sum等会要不断减少,会变化,所以要有个比较和大小的参照,我们也假设sum此时就是最大
      let sum = windowSum;
      while (k > 0) {
        windowSum = windowSum - cardPoints[k - 1] + cardPoints[n];
        sum = Math.max(windowSum, sum);
        k--;
        n--;
      }
      return sum;
    };

    滑动窗口-可获得的最大点数 Maximum Points You Can Obtain from Cards

    原问题等价为:从 cardPoints 中找长度为 n - k 的连续段,使其总和最小。

    var maxScore = function (cardPoints, k) {
      const total = cardPoints.reduce((a, b) => a + b);
      // 滑动窗口大小为 length - k
      let windowSize = cardPoints.length - k, windowSum = 0;
      // 选前 n-k 个作为初始值
      for (let i = 0; i < windowSize; i++) {
        windowSum += cardPoints[i];
      }
      let minSum = windowSum;
      for (let i = windowSize; i < cardPoints.length; i++) {
        // 滑动窗口每向右移动一格,增加从右侧进入窗口的元素值,并减少从左侧离开窗口的元素值
        windowSum = windowSum + cardPoints[i] - cardPoints[i - windowSize];
        minSum = Math.min(windowSum, minSum);
      }
      return total - minSum;
    };

    上面是官方解法,但是还不如最上面的解法。这个是n+k。最上面的是2k

    长度最小的子数组

    https://leetcode.cn/problems/minimum-size-subarray-sum/description/

    找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

    示例 1:输入:target = 7, nums = [2,3,1,2,4,3]            输出:2    解释:子数组 [4,3] 是该条件下的长度最小的子数组。

    示例 2:输入:target = 4, nums = [1,4,4]                    输出:1

    示例 3:输入:target = 11, nums = [1,1,1,1,1,1,1,1]    输出:0

    https://programmercarl.com/0209.长度最小的子数组.html

    连续子数组图解滑动窗口过程滑动窗口.长度最小的子数组

    var minSubArrayLen = function (target, nums) {
      let start = 0, end = 0;
      let windowSum = 0, minLength = Infinity;
      while (end < nums.length) {
        windowSum = windowSum + nums[end];//窗口扩张:向右移动右指针,将新元素纳入窗口
        while (windowSum >= target) {// 检查当前窗口是否满足条件
          minLength = Math.min(minLength, end - start + 1);
          windowSum = windowSum - nums[start];//窗口收缩:尝试缩短窗口,移除左侧元素,更新窗口和
          start++;
          // 若左侧指针已经越过右侧指针,跳出内层循环
          if (start > end) {
            break;
          }
        }
        end++;
      }
      return Number.isFinite(minLength) ? minLength : 0;
    };


    最长重复子数组

    https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

    给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。

    示例 1:输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]   输出:3  解释:长度最长的公共子数组是 [3,2,1] 。

    示例 2:输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]   输出:5


    动态规划

    动态规划是一种将复杂问题分解为若干个子问题,并存储子问题的解以避免重复计算的优化策略。对于“最长重复子数组”问题,

    leetcode第718题求长度最长的公共子数组的解析  718. 最长重复子数组

    如果没有整明白,可以看这个:

    function findLength(nums1, nums2) {
      const [m, n] = [nums1.length, nums2.length];
      let maxLen = 0;
      const gird = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); // dp数组初始化,都初始化为0
      for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
          if (nums1[i - 1] === nums2[j - 1]) { // 当前元素相等
            gird[i][j] = gird[i - 1][j - 1] + 1; // 根据状态转移方程更新 dp 值
            maxLen = Math.max(maxLen, gird[i][j]); // 更新最长子数组长度
          }
        }
      }
      return maxLen;
    }


    以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。我就定义dp[i][j]为 以下标i为结尾的A,和以下标j 为结尾的B,最长重复子数组长度。不行么?当然可以,就是实现起来麻烦一些。

    滚动数组

    dp[i][j]都是由dp[i - 1][j - 1]推出。那么压缩为一维数组,也就是dp[j]都是由dp[j - 1]推出。也就是相当于可以把上一层dp[i - 1][j]拷贝到下一层dp[i][j]来继续用。此时遍历B数组的时候,就要从后向前遍历,这样避免重复覆盖。

    滑动窗口

    const findLength = (nums1, nums2) => {
      let len1 = nums1.length, len2 = nums2.length;
      // dp[i][j]: 以nums1[i-1]、nums2[j-1]为结尾的最长公共子数组的长度
      let dp = new Array(len2 + 1).fill(0);
      let res = 0;
      for (let i = 1; i <= len1; i++) {
        for (let j = len2; j > 0; j--) {
          if (nums1[i - 1] === nums2[j - 1]) {
            dp[j] = dp[j - 1] + 1;
          } else {
            dp[j] = 0;
          }
          res = Math.max(res, dp[j]);
        }
      }
      return res;
    };

    这个在捋一下,用滑动窗口也是可以解的。

    滑动窗口

    这个滑动窗口的写法跟一般滑动窗口写法不太一样,一般滑动窗口只要移动指针就完事了,这个滑动窗口其实不应该看成滑动窗口,而应该去找规律。leetcode题解里面对这题虽然动图意思对的,但是顺序以及注意点都有强烈误导性,导致正常人看了动图压根写不出这种循环。所以我拿别人图将顺序和过程以及注意点改造了下:

    20200701092536977.jpg

    var findLength = function (nums1, nums2) {
      let result = 0;
      const len1 = nums1.length, len2 = nums2.length;
      const total = len1 + len2;
      for (let i = 0; i < total; i++) {
        let start1 = 0, start2 = 0, winowSize = 0;
        if (i < len1) {
          start1 = len1 - i - 1;// 其实就是先固定num1,所以先取num1从后往前取
          start2 = 0;// 那么num2就是从前往后取
          winowSize = i + 1;
        } else {// 与上面相反
          start1 = 0;
          start2 = i - len1;
          winowSize = Math.min(len2 - start2, len1);
        }
        const res = maxLength(nums1, nums2, start1, start2, winowSize);
        result = Math.max(result, res);
      }
      return result;
    };
    
    function maxLength(num1, num2, start1, start2, windowSize) {
      let count = 0, max = 0;
      for (let i = 0; i < windowSize; i++) {
        if (num1[start1 + i] === num2[start2 + i]) {
          count++;
          max = Math.max(count, max);
        } else {
          count = 0;
        }
      }
      return max;
    }

    其实这个写法看起来挺晕的,还不如官方代码简洁:

    function findLength(num1, num2) {
      let result = 0;
      const len1 = num1.length;
      const len2 = num2.length;
      for (let start1 = 0; start1 < len1; start1++) {// 固定数组1
        const windowSize = Math.min(len1 - start1, len2);
        const res = maxLength(num1, num2, start1, 0, windowSize);
        result = Math.max(result, res);
      }
      for (let start2 = 0; start2 < len2; start2++) { // 固定数组2
        const windowSize = Math.min(len1, len2 - start2);
        const res = maxLength(num1, num2, 0, start2, windowSize);
        result = Math.max(result, res);
      }
      return result;
    }
    
    function maxLength(num1, num2, start1, start2, windowSize) {
      let max = 0;
      let count = 0;
      for (let i = 0; i < windowSize; i++) {
        if (num1[start1 + i] === num2[start2 + i]) {
          count++;
          max = Math.max(count, max);
        } else {
          count = 0;
        }
      }
      return max;
    }

    最长重复子数组        最长重复子数组       最长重复子数组 滑动窗口

     

    字符串系列

    回文字符串 题目很多,比如:

    1. 反转字符串(LeetCode 344):给定一个字符串,判断其是否可以通过调整字符顺序来形成回文串。

    2. 最长回文子串(LeetCode 5):给定一个字符串,找到其中最长的回文子串。

    3. 回文子串计数(LeetCode 647):给定一个字符串,统计其中回文子串的数量。

    4. 分割回文串(LeetCode 131):给定一个字符串,将其分割成若干个回文子串,返回所有可能的分割方案。

    我们看最长回文字符串与 回文子串计数 都可以 分离双指针。

    中心扩展法(分离双指针)

    最长回文子串/回文子串计数

    https://leetcode.cn/problems/longest-palindromic-substring/description/

    其实就是分离双指针:遍历每一个字符,向两边扩展找到以其为中心的最长回文子串, 所有找到的回文子串的最大长度即所求 。

    image.png

    不过,以当前字符为中心的回文串的长度可能是奇数,也可能是偶数,两种情况都需要考察:

    最长回文字符串,奇数的情况最长回文字符串,偶数的情况


    var longestPalindrome = function (s) {
      if (typeof s !== 'string' || s.length < 1) return s;
      let start = 0, end = 0;
      for (let i = 0; i < s.length; i++) {
        //奇数长: 以当前字符为中心向两边扩展,
        const { left: left1, right: right1 } = expandAroundCenter(s, i, i);
        //偶数长: 以当前字符和下一个字符的间隔为中心向两边扩展
        const { left: left2, right: right2 } = expandAroundCenter(s, i, i + 1);
        const len1 = right1 - left1 + 1;
        const len2 = right2 - left2 + 1;
        if (len1 > len2) {
          if (end - start < len1) {
            start = left1;
            end = right1;
          }
        } else {
          if (end - start < len2) {
            start = left2;
            end = right2;
          }
        }
      }
      // JavaScript 的 substring 函数截取子串,end + 1 是因为 substring 函数截取的结束位置是开区间
      return s.substring(start, end + 1);
    };
    
    function expandAroundCenter(s, left, right) {// 找到以 left 和 right 为中心向两边扩展的最长回文子串长度
      while (left >= 0 && right < s.length && s[left] === s[right]) {// 循环直到边界或不是回文串为止
        left--;
        right++;
      }
      return { left: left + 1, right: right - 1 };
    }

    特别说明下:

    • const len1 = expandAroundCenter(s, i, i);:这里我们将当前字符s[i] 作为回文字符串的中心,即左右边界都是 i。这种情况下,回文字符串的长度为奇数。例如,对于字符串 "babad",当 i = 2 时,s[i] 是字符 'a',以 'a' 为中心的回文字符串有 "bab" 和 "aba",其中最长的是 "bab",长度为 3。

    • const len2 = expandAroundCenter(s, i, i + 1);:这里我们将当前字符 s[i] 和下一个字符 s[i + 1] 作为回文字符串的中心即左边界是 i,右边界是 i + 1。这种情况下,回文字符串的长度为偶数。例如,对于字符串 "babad",当 i = 1 时,s[i] 和 s[i + 1] 分别是字符 'a' 和 'b',以 'a' 和 'b' 为中心的回文字符串有 "aba",长度为 3。

    也可以用动态规划来做……

    分割回文字符串,必须得用回溯+动态规划,或者 回溯 + 记忆化搜索

    回文字符串动态规划解法

    可以参看DP笔记(3):二维线性DP问题:最长公共子序列/最长重复子数组




    转载本站文章《双指针:对撞/快慢/分离/滑动窗口的案例(数组/回文/求和等)》,
    请注明出处:https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9093.html