Leetcode算法入门与数组丨6. 数组双指针、滑动窗口

1 双指针基础知识

1.1 双指针简介

双指针（Two Pointers） 是一种常用的算法技巧，通常用于在数组或链表中进行遍历或搜索。它使用两个指针在不同的位置上移动，以解决特定的问题。

双指针常见的应用场景包括：

1. 快慢指针：两个指针方向相同，但是使用两个指针以不同的速度遍历链表，用于解决链表中的环检测、链表中点、链表倒数第k个节点等问题。
2. 左右指针（对撞指针）：在有序数组中，使用两个指针从数组的两端向中间移动，以解决查找目标值、两数之和、三数之和等问题。
3. 分离双指针：两个指针分别属于不同的数组/链表。

双指针算法通常具有较低的时间复杂度，并且可以在一次遍历中完成任务，因此在很多问题中都有很好的应用。

1.2 左右指针（对撞指针）

左右指针（Left and Right Pointers）是双指针算法中的一种常见技巧。它通常用于在有序数组或字符串中查找目标值、寻找满足某种条件的子序列等问题。

左右指针的基本思想是，使用两个指针分别指向数组或字符串的左右两端，然后根据问题的要求，通过移动指针的位置来逼近或搜索目标。

基本步骤

1. 两个指针 $left$ 和 $right$。 $left$ 指向序列第一个元素（ $left=0$ ），$right$ 指向序列最后一个元素（ $right=len(nums)-1$ ）。
2. 循环体中将左右指针相向移动，当满足一定条件时，将左指针右移（$left+=1$ ）。当满足另外一定条件时，将右指针左移（$right+=1$ ）。
3. 直到两个指针相撞（$left=right$ ），或者满足其他要求的特殊条件时，跳出循环体。

伪代码模板

left, right = 0, len(nums) - 1

while left < right:
    if 满足要求的特殊条件:
        return 符合条件的值 
    elif 一定条件 1:
        left += 1
    elif 一定条件 2:
        right -= 1

return 没找到 或 找到对应值
1
2
3
4
5
6
7
8
9
10
11

适用范围

1. 有序数组或有序链表：左右指针可以在有序数组或有序链表中进行查找、搜索、比较等操作。通过左右指针的移动，可以快速定位目标值或满足特定条件的元素。

2. 滑动窗口问题：滑动窗口问题通常涉及在数组或字符串上定义一个窗口，并通过移动窗口的左右边界来解决问题。左右指针可以用于表示窗口的左右边界，并根据问题的要求进行移动和调整。

3. 两数之和、三数之和等问题：在有序数组中查找满足特定条件的数对或数组合时，左右指针可以进行逼近，快速找到满足条件的解。

4. 回文字符串判断：左右指针可以用于判断字符串是否是回文字符串。通过左右指针从两端向中间移动，并比较对应位置的字符是否相等，可以判断字符串是否是回文。

1.3 快慢指针

快慢指针（Fast and Slow Pointers）基本思想是使用两个指针，一个指针（快指针 fast）移动速度较快，另一个指针（慢指针 slow）移动速度较慢。通过两个指针的相对移动，可以得到一些有用的信息，从而解决问题。

基本步骤

1. 初始化快慢指针：将快指针和慢指针都指向链表的头节点或数组的起始位置。$slow=0,fast=1或0$

2. 移动指针：根据问题的要求，通过移动快慢指针来逼近目标或获取有用的信息。

   • 快指针移动：通常每次移动两步或一步，可以快速遍历整个链表或数组。$fast+=1$
   • 慢指针移动：通常每次移动一步，慢指针的移动速度较慢。$slow+=1$

3. 判断终止条件：根据问题的要求，判断是否满足终止条件。

   • 例如，在链表中环检测问题中，如果快指针和慢指针相遇，则存在环；如果快指针到达链表末尾，则不存在环。

4. 根据问题的要求返回结果。

   • 例如，在链表中找到中间节点的问题中，当快指针到达链表末尾时，慢指针所指的节点就是中间节点。

伪代码模板

slow = 0
fast = 1
while 没有遍历完：
    if 满足要求的特殊条件:
        slow += 1
    fast += 1
return 合适的值
1
2
3
4
5
6
7

适用范围

1. 链表中的环检测：快慢指针可以用于判断链表中是否存在环。快指针每次移动两步，慢指针每次移动一步，如果链表中存在环，则快指针最终会追上慢指针，二者相遇。

2. 链表中点的查找：快慢指针可以用于找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针正好在链表的中间位置。

3. 链表倒数第k个节点的查找：快慢指针可以用于定位链表的倒数第k个节点。快指针先移动k个位置，然后快慢指针同时向前移动，当快指针到达链表末尾时，慢指针所指的节点就是倒数第k个节点。

4. 判断链表是否有交点：快慢指针可以用于判断两个链表是否相交。分别使用快慢指针遍历两个链表，如果两个链表相交，则快指针和慢指针最终会相遇。

5. 数组中的重复元素查找：快慢指针可以用于在数组中查找重复元素。通过快慢指针的移动，可以找到数组中的重复元素或判断数组是否存在重复元素。

1.4 分离双指针

分离双指针（Two Pointers with Separation）是一种双指针算法的变体，它通常用于解决数组或链表中需要分离的问题，例如将奇偶数分离、将0和非0元素分离等。分离双指针的基本思想是使用两个指针，一个指针（分离指针）用于分离元素，另一个指针（遍历指针）用于遍历数组或链表。通过移动遍历指针，并根据特定条件将元素交换到分离指针的位置，实现元素的分离。

基本步骤

1. 两个指针 $lef{t}_1$、$lef{t}_2$ 。 $lef{t}_1$ 指向第一个数组的第一个元素（ $lef{t}_1=0$）， $lef{t}_2$ 指向第二个数组的第一个元素（ $lef{t}_2=0$）。

2. 当满足一定条件时

   1. 两个指针同时右移，$lef{t}_1+=1、lef{t}_2+=1$。

   2. $lef{t}_1$ 右移，$lef{t}_1+=1$。

   3. $lef{t}_2$ 右移，$lef{t}_2+=1$。

3. 当其中一个数组遍历完时或者满足其他特殊条件时跳出循环体。

伪代码模板

left_1 = 0
left_2 = 0

while left_1 < len(nums1) and left_2 < len(nums2):
    if 一定条件 1:
        left_1 += 1
        left_2 += 1
    elif 一定条件 2:
        left_1 += 1
    elif 一定条件 3:
        left_2 += 1
1
2
3
4
5
6
7
8
9
10
11

适用范围

分离双指针一般用于处理有序数组合并，求交集、并集问题

349. 两个数组的交集 - 力扣（LeetCode）

思路：分离双指针

1. 两个数组先排序。（$nums1、nums2$）
2. 使用两个指针分别指向两个数组的第一个元素，即第一个指针指向第一个数组的第一个元素，第二个指针指向第二个数组的第一个元素。（$lef{t}_1=0、lef{t}_2=0$）
3. 如果 $nums1[lef{t}_1]==nums2[lef{t}_2]$ 则将其加入答案数组（注意去重），并将 $lef{t}_1$ 和 $lef{t}_2=0$ 右移 （$lef{t}_1+=1$ 、$lef{t}_2+=1$）。
4. 如果 $nums1[lef{t}_1]<nums2[lef{t}_2]$ ，则 $lef{t}_1$ 右移 。
5. 如果 $nums1[lef{t}_1]>nums2[lef{t}_2]$ ，则 $lef{t}_2$ 右移 。
6. 返回答案。

代码

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()

        left_1 = 0
        left_2 = 0
        res = []
        while left_1 < len(nums1) and left_2 < len(nums2):
            if nums1[left_1] == nums2[left_2]:
                if nums1[left_1] not in res:
                    res.append(nums1[left_1])
                left_1 += 1
                left_2 += 1
            elif nums1[left_1] < nums2[left_2]:
                left_1 += 1
            elif nums1[left_1] > nums2[left_2]:
                left_2 += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2 滑动窗口基础知识

2.1 滑动窗口算法介绍

滑动窗口算法（Sliding Window Algorithm）是一种常用的算法技巧，用于解决数组或字符串相关的问题。它的基本思想是维护一个窗口，通过在数组或字符串上滑动窗口，不断更新窗口内的状态，从而解决问题。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。

• 滑动操作：窗口向一个方向移动，常见的是向右侧移动。
• 缩放操作：针对不固定长度的窗口，可以从左侧缩小窗口长度，也可以从右侧扩大窗口长度。

2.2 滑动窗口适用范围

滑动窗口算法通常适用于线性数据结构，如数组和字符串。它在处理大规模数据时特别有用，因为它可以通过滑动窗口的方式，仅对部分数据进行处理，而不需要遍历整个数据集。这使得滑动窗口算法具有较低的时间复杂度，并且在实际应用中常常能够提供高效的解决方案。

按照窗口长度的固定情况，我们可以将滑动窗口题目分为以下两种：

• 固定长度窗口：窗口大小是固定的。

• 不定长度窗口

  • 窗口大小是不固定的。

  • 求解最大的满足条件的窗口。

  • 求解最小的满足条件的窗口。

2.3 固定长度滑动窗口

固定长度滑动窗口是一种特殊的滑动窗口算法，它的窗口大小固定，不会随着数据集的变化而变化。该算法通常用于需要对连续的数据序列进行处理的问题，如时间序列数据分析等。

固定长度滑动窗口的基本思想是：将数据序列分成若干个固定长度的子序列，然后对每个子序列进行处理。在处理每个子序列时，可以使用滑动窗口算法，通过移动窗口来更新子序列内的状态，从而得到最终的结果。

基本步骤

固定长度滑动窗口的步骤如下：

1. 初始化窗口的起始位置和结束位置，窗口大小固定。
2. 对于每个窗口内的子序列，根据问题要求更新窗口内的状态。
3. 如果窗口满足特定条件，记录结果。
4. 继续移动窗口的起始位置，重复上述步骤，直到遍历完整个数据集。

代码模板

left = 0
right = 0

while right < len(nums):
    window.append(nums[right])
    
    # 超过窗口大小时，缩小窗口，维护窗口中始终为 window_size 的长度
    if right - left + 1 >= window_size:
        # ... 维护答案
        window.popleft()
        left += 1
    
    # 向右侧增大窗口
    right += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.4 不固定长度滑动窗口

不定长度滑动窗口算法（Sliding Window）：在给定数组 / 字符串上维护一个不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。

基本步骤

1. 使用两个指针 $left$、$right$。初始时，$left$、$right$ 都指向序列的第一个元素。即：$left=0$，$right=0$，区间 $[left,right]$ 被称为一个「窗口」。
2. 将区间最右侧元素添加入窗口中，即 window.add(s[right])。
3. 然后向右移动 $right$，从而增大窗口长度，即 right += 1。直到窗口中的连续元素满足要求。
4. 此时，停止增加窗口大小。转向不断将左侧元素移出窗口，即 window.popleft(s[left])。
5. 然后向右移动 $left$，从而缩小窗口长度，即 left += 1。直到窗口中的连续元素不再满足要求。
6. 重复 2 ~ 5 步，直到 $right$ 到达序列末尾。

代码模板

left = 0
right = 0

while right < len(nums):
    window.append(nums[right])
    
    while 窗口需要缩小:
        # ... 可维护答案
        window.popleft()
        left += 1
    
    # 向右侧增大窗口
    right += 1
1
2
3
4
5
6
7
8
9
10
11
12
13

参考文献

• [1] https://datawhalechina.github.io/leetcode-notes/#/

—— END ——

---

如果以上内容有任何错误或者不准确的地方，欢迎在下面 👇 留言。或者你有更好的想法，欢迎一起交流学习~~~

更多精彩内容请前往 AXYZdong的博客