• home > theory > algorithm > leetcode >

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

    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]

    这个解释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/

    解释: 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/

    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;
    };

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

    滑动窗口

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

    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