LeetCode-题目详解（九）：双指针【left/right指针；slow/fast指针】、滑动窗口、多指针

刺骨的言语ヽ痛彻心扉 2023-10-04 13:31 20阅读 0赞

#### 这里写目录标题 ####

*  一、双指针/滑动窗口介绍
 *  二、Leetcode案例
 *   *  11. 盛最多水的容器
     *  15. 三数之和【剑指 Offer II 007. 数组中和为 0 的三个数】
     *  16. 最接近的三数之和
     *  28. 找出字符串中第一个匹配项的下标【实现strStr()】
     *  125. 验证回文串
     *  26. 删除有序数组中的重复项
     *  27. 移除元素
     *  283. 移动零
     *  80. 删除有序数组中的重复项 II
     *  344-反转字符串
     *  3-无重复字符的最长子串【剑指 Offer 48. 最长不含重复字符的子字符串】
     *  424-替换后的最长重复字符
     *  剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
     *  剑指 Offer 57. 和为s的两个数字
     *   *  方法一：双指针
     *  剑指 Offer 57 - II. 和为s的连续正数序列
     *   *  方法一：滑动窗口
         *  方法二：滑动窗口
     *  151. 反转字符串中的单词【剑指 Offer 58 - I. 翻转单词顺序】
     *   *  方法一：双指针
     *  264. 丑数 II【剑指 Offer 49. 丑数】
     *   *  方法一：三指针
     *  287. 寻找重复数
     *  349. 两个数组的交集
     *  350. 两个数组的交集 II
     *   *  方法一：
         *  方法二：
     *  392. 判断子序列
     *  面试题 01.05. 一次编辑
     *  剑指 Offer 59 - I. 滑动窗口的最大值
     *  面试题 16.06. 最小差
     *  面试题 16.24. 数对和
     *  209. 长度最小的子数组
     *  剑指 Offer 58 - II. 左旋转字符串
     *  763. 划分字母区间

## 一、双指针/滑动窗口介绍 ##

滑动窗口法是指通过 left 以及 right 指针来框定一个窗口，当在窗口内的字符串满足题目要求则记录下当前窗口长度并进一步扩张寻找更长的窗口，若不满足则进行窗口平移。

**滑动窗口法的模板**

def findSubstring(s):
        left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
        dict = {
       
        }  # 用于统计 子数组/子区间 是否有效
        result = 0 # 保存最大的满足题目要求的 子数组/子串 长度
        while right < len(s): # 当右边的指针没有搜索到 数组/字符串 的结尾
            dict[s[right]] = dict.get(s[right], 0) + 1 # 增加当前右边指针的数字/字符的计数
            while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
                dict[s[left]] -= 1 # 移动左指针前需要从 dict 中减少left位置字符的计数
                left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
            # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
            result = max(result, right - left + 1) # 需要更新结果
            right += 1 # 移动右指针，去探索新的区间
        return result

简单介绍上面的模板，模板的思想是：**以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。**

模板的整体思想是：

1.  定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 dict 用来统计该区间内的各个字符出现次数；
2.  第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的计数；
3.  第二重 while 循环是让 left 指针向右移动到 \[left, right\] 区间符合题意的位置；当 left 每次移动到了新位置，需要减少 left 指针的计数；
4.  在第二重 while 循环之后，成功找到了一个符合题意的 \[left, right\] 区间，题目要求最大的区间长度，因此更新 result 为 max(result, 当前区间的长度) 。
5.  right 指针每次向右移动一步，开始探索新的区间。

模板中为什么不把 dict 放在 while 循环内部呢？因为如果放在 while 内部每次新建一个 dict 变量，统计区间的字符出现次数的时间复杂度是 O(N) ；放在 while 外部，每次增加 right 指向的字符的计数、减少 left 指向的字符的计数的是时间复杂度是 O(1) 。这也是常见的统计区间问题时的技巧。类似的，如果我们要求一个区间的和的话，也可以用类似的思想去做。

## 二、Leetcode案例 ##

### 11. 盛最多水的容器 ###

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height\[i\]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：  
![在这里插入图片描述][85619c31abdd4aa48817874585cede00.png]

输入：[1,8,6,2,5,4,8,3,7]
    输出：49 
    解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
    输出：1

提示：

*  n == height.length
 *  2 <= n <= 105
 *  0 <= height\[i\] <= 104

--------------------

class Solution:
        def maxArea(self, height: List[int]) -> int:
            left, right = 0, len(height) - 1
            result = 0
            while left < right:
                area = min(height[left], height[right]) * (right - left)
                result = max(result, area)
                if height[left] <= height[right]:
                    left += 1
                else:
                    right -= 1
            return result

class Solution {
       
        
    public:
        int maxArea(vector<int>& height) {
       
        
            int left = 0, right = height.size() - 1;
            int result = 0;
            while(left < right){
       
        
                int area = min(height[left], height[right]) * (right - left);
                result = max(result, area);
                if(height[left] <= height[right]){
       
        
                    left++;
                }else{
       
        
                    right--;
                }
            }
            return result;
        }
    };

### 15. 三数之和【剑指 Offer II 007. 数组中和为 0 的三个数】 ###

给你一个整数数组 nums ，判断是否存在三元组 \[nums\[i\], nums\[j\], nums\[k\]\] 满足 i != j、i != k 且 j != k ，同时还满足 nums\[i\] + nums\[j\] + nums\[k\] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]
    解释：
    nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
    nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
    nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
    不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
    注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
    输出：[]
    解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
    输出：[[0,0,0]]
    解释：唯一可能的三元组和为 0 。

提示：

*  3 <= nums.length <= 3000
 *   − 1 0 5 < = n u m s \[ i \] < = 1 0 5 -10^5 <= nums\[i\] <= 10^5 −105<=nums\[i\]<=105

--------------------

class Solution {
       
        
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
       
        
            sort(nums.begin(), nums.end());
            vector<vector<int>> result;
    
            for(int i = 0; i < nums.size() - 2; i++){
       
        
                if(i > 0 && nums[i] == nums[i - 1]){
       
        
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while(left < right){
       
        
                    int sum3 = nums[i] + nums[left] + nums[right];
                    if(sum3 == 0){
       
        
                        result.push_back({
       
        nums[i], nums[left], nums[right]});
                        while(left < right && nums[left] == nums[left + 1]){
       
        
                            left++;
                        }
                        while(left < right && nums[right] == nums[right - 1]){
       
        
                            right--;
                        }
                        left++;
                        right--;
                    }else if(sum3 < 0){
       
        
                        left++;
                    }else{
       
        
                        right--;
                    }
                }
            }
            return result;
        }
    };

class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            nums.sort()
            result = []
    
            for i in range(len(nums) - 2):
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                left = i + 1
                right = len(nums) - 1
                while left < right:
                    sum3 = nums[i] + nums[left] + nums[right]
                    if sum3 == 0:
                        result.append([nums[i], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif sum3 < 0:
                        left += 1
                    else:
                        right -= 1
            
            return result

### 16. 最接近的三数之和 ###

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
    输出：2
    解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1
    输出：0

提示：

*  3 <= nums.length <= 1000
 *  \-1000 <= nums\[i\] <= 1000
 *   − 1 0 4 < = t a r g e t < = 1 0 4 -10^4 <= target <= 10^4 −104<=target<=104

--------------------

class Solution {
       
        
    public:
        int threeSumClosest(vector<int>& nums, int target) {
       
        
            sort(nums.begin(), nums.end());
            int result = nums[0] + nums[1] + nums[2];
            for(int i = 0; i < nums.size(); i++){
       
        
                int left = i + 1;
                int right = nums.size() - 1;
                while(left < right){
       
        
                    int sum3 = nums[i] + nums[left] + nums[right];
                    if(abs(sum3 - target) < abs(result - target)){
       
        
                        result = sum3;
                    }
                    if(sum3 > target){
       
        
                        right--;
                    }else{
       
        
                        left++;
                    }
                }
            }
    
            return result;
        }
    };

class Solution:
        def threeSumClosest(self, nums: List[int], target: int) -> int:
            nums.sort()
            result = float('inf')
            for i in range(len(nums)):
                left = i + 1
                right = len(nums) - 1
                while left < right:
                    sum3 = nums[i] + nums[left] + nums[right]
                    if abs(sum3 - target) < abs(result - target):
                        result = sum3
                    if sum3 > target:
                        right -= 1
                    else:
                        left += 1
    
            return result

### 28. 找出字符串中第一个匹配项的下标【实现strStr()】 ###

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
    输出：0
    解释："sad" 在下标 0 和 6 处匹配。
    第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
    输出：-1
    解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

*  1 <= haystack.length, needle.length <=  1 0 4 10^4 104
 *  haystack 和 needle 仅由小写英文字符组成

--------------------

class Solution:
        def strStr(self, haystack: str, needle: str) -> int:
            left = 0
            right = len(needle)
    
            while right <= len(haystack):
                if haystack[left:right] == needle:
                    return left
                left += 1
                right += 1
            return -1

class Solution {
       
        
    public:
        int strStr(string haystack, string needle) {
       
        
            if(needle.size() > haystack.size()){
       
        
                return -1;
            }
            
            int left = 0;
            int len = needle.size();
    
            while(left <= haystack.size() - len){
       
        
                if(haystack.substr(left, len) == needle){
       
        
                    return left;
                }
                left++;
            }
            return -1;
        }
    };

### 125. 验证回文串 ###

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama"
    输出：true
    解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"
    输出：false
    解释："raceacar" 不是回文串。

示例 3：

输入：s = " "
    输出：true
    解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
    由于空字符串正着反着读都一样，所以是回文串。

提示：

*  1 <= s.length <= 2 \* 105
 *  s 仅由可打印的 ASCII 字符组成

--------------------

class Solution:
        def isPalindrome(self, s: str) -> bool:
            sgood = "".join(ch.lower() for ch in s if ch.isalnum())
    
            n = len(sgood)
            left, right = 0, n - 1
            
            while left < right:
                if sgood[left] != sgood[right]:
                    return False
                left += 1
                right -= 1
            
            return True

class Solution {
       
        
    public:
        bool isPalindrome(string s) {
       
        
            string sgood;
            for (char ch: s) {
       
        
                if (isalnum(ch)) {
       
        
                    sgood += tolower(ch);
                }
            }
    
            int n = sgood.size();
            int left = 0, right = n - 1;
    
            while (left < right) {
       
        
               if (sgood[left] != sgood[right]) {
       
        
                    return false;
                }
                left++;
                right--;
            }
            
            return true;
        }
    };

### 26. 删除有序数组中的重复项 ###

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
    int[] expectedNums = [...]; // 长度正确的期望答案
    
    int k = removeDuplicates(nums); // 调用
    
    assert k == expectedNums.length;
    for (int i = 0; i < k; i++) {
        assert nums[i] == expectedNums[i];
    }

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]
    输出：2, nums = [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]
    解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

*  0 <= nums.length <= 3 \*  1 0 4 10^4 104
 *   − 1 0 4 < = n u m s \[ i \] < = 1 0 4 -10^4 <= nums\[i\] <= 10^4 −104<=nums\[i\]<=104
 *  nums 已按升序排列

--------------------

class Solution:
        def removeDuplicates(self, nums: List[int]) -> int:
            left = 0
            right = 0
            while right < len(nums):
                right += 1                                          # 右指针作为驱动指针
                if right < len(nums) and nums[right] != nums[left]: # 当右指针元素≠左指针元素时，左指针右移一位
                    left += 1
                    nums[left], nums[right] = nums[right], nums[left]
    
            return left + 1

class Solution {
       
        
    public:
        int removeDuplicates(vector<int>& nums) {
       
        
            int left = 0;
            int right = 0;
            while(right < nums.size()){
       
        
                right++;												// 右指针作为驱动指针
                if(right < nums.size() && nums[right] != nums[left]){
       
        	// 当右指针元素≠左指针元素时，左指针右移一位
                    left ++;
                    swap(nums[left], nums[right]);
                }
            }
            return left + 1;
        }
    };

### 27. 移除元素 ###

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
    int len = removeElement(nums, val);
    
    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }

示例 1：

输入：nums = [3,2,2,3], val = 3
    输出：2, nums = [2,2]
    解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0

[85619c31abdd4aa48817874585cede00.png]: https://img-blog.csdnimg.cn/85619c31abdd4aa48817874585cede00.png