• home > theory > algorithm > leetcode >

    双指针相关问题(滑动窗口/反转字符串/回文字串)总结

    Date:

    回顾《数组二分查找到二分法的感悟笔记》,其实二分查找就是双指针。对于双指针,特别推荐:【双指针超清晰动画演示】从一个简单模型到双指

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


    双指针的种类

    对撞指针

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

    对撞指针

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

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

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

     快慢指针

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

    快慢指针

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

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

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

    分离双指针

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

    分离双指针


    双指针的题包括

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    18. 删除排序数组中的重复项(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/squares-of-a-sorted-array/

    这个解释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 ,返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

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

    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. 反转字符串(LeetCode 344):给定一个字符串,判断其是否可以通过调整字符顺序来形成回文串。

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

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

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

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

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

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

    其实就是分离双指针

    // 找到以 left 和 right 为中心向两边扩展的最长回文子串长度
    function expandAroundCenter(s, left, right) {
      // 循环直到边界或不是回文串为止
      while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--;  // 向左移动指针
        right++; // 向右移动指针
      }
      // 返回回文串的长度
      return right - left - 1; // 减1是因为循环结束时左右指针各多移动了一次
    }
    
    function longestPalindrome(s) {
    
      if (s === null || s.length < 1) return "";
    
      let start = 0; // 记录回文串的起始位置
      let end = 0;   // 记录回文串的结束位置
    
      // 遍历字符串
      for (let i = 0; i < s.length; i++) {
        //奇数长: 以当前字符为中心向两边扩展,
        let len1 = expandAroundCenter(s, i, i);
        //偶数长: 以当前字符和下一个字符的间隔为中心向两边扩展
        let len2 = expandAroundCenter(s, i, i + 1);
        // 计算以当前字符或字符间隔为中心的最长回文子串长度
        let len = Math.max(len1, len2);
    
        // 如果找到的回文串比当前记录的长,则更新起始和结束位置
        if (len > end - start) {
          start = i - Math.floor((len - 1) / 2);
          end = i + Math.floor(len / 2);
        }
      }
    
      // 返回最长回文子串
      return s.substring(start, end + 1); // JavaScript 的 substring 函数截取子串,end + 1 是因为 substring 函数截取的结束位置是开区间
    }
    
    // 示例
    console.log(longestPalindrome("babad")); // 输出 "bab" 或 "aba"
    console.log(longestPalindrome("cbbd")); // 输出 "bb"

    特别说明下:

    • 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。

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


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


    转载本站文章《双指针相关问题(滑动窗口/反转字符串/回文字串)总结》,
    请注明出处:https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9093.html