一、滑窗算法

滑窗算法是一种用于处理数组/链表子区间问题的高效技巧，通过维护一个窗口来减少计算量。

1、基本思想

• 维护一个窗口（通常由两个指针表示左右边界）
• 移动右指针扩展窗口直到满足条件
• 然后移动左指针收缩窗口直到不满足条件
• 在移动过程中记录所需信息

2、经典例题

• 问题：求长度为 k 的子数组最大平均数

# 求长度为 k 的子数组最大平均数
def findMaxAverage(nums, k):
    cur = sum(nums[:k])
    ans = cur
    for right in range(k, len(nums)):
        cur += nums[right] - nums[right - k]
        ans = max(ans, cur)
    return ans / k

s = [2,1,2,5,3,6,4,3,6,4,6,5,4,2,80,5,7,8,5,4,]
print(findMaxAverage(s,2)) #输出：42.5

• 问题：给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

# 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
# 示例：
# 输入: s = "pwwkew"
# 输出: 3
# 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
#      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
def lengthOfLongestSubstring(s):
    left = 0
    seen = set()
    ans = 0
    for right, c in enumerate(s):
        while c in seen:
            seen.remove(s[left])
            left += 1
        seen.add(c)
        ans = max(ans, right - left + 1)
    return ans

s = "pwwkew"
print(lengthOfLongestSubstring(s))# 3

二、双指针算法

双指针算法使用两个指针以不同策略遍历数据结构，通常用于优化暴力解法。

1、常见类型

• 同向双指针：两个指针从同一侧开始移动
• 对向双指针：两个指针分别从首尾向中间移动
• 快慢指针：一个指针移动快，一个移动慢

2、代码模版

def two_pointers(nums):
    left, right = 0, len(nums) - 1  # 或根据问题调整初始化
    
    while left < right:  # 或其他终止条件
        if condition1:
            left += 1
        elif condition2:
            right -= 1
        else:
            # 处理结果
            left += 1
            right -= 1
    
    return result

典型应用

• 两数之和（有序数组）
• 三数之和
• 盛最多水的容器
• 移除元素
• 链表中的环检测

3、示例

问题：判断链表有环无环

class ListNode:
    """单链表节点"""
    def __init__(self, val=0, next=None):
        self.val  = val
        self.next = next

def has_cycle(head: ListNode) -> bool:
    """
    快慢指针：若相遇则有环，否则无环
    """
    slow = fast = head
    while fast and fast.next:          # fast 走两步，必须检查 fast.next 存在
        slow = slow.next               # 慢指针走一步
        fast = fast.next.next          # 快指针走两步
        if slow is fast:               # 相遇 => 有环
            return True
    return False                       # fast 先到 None => 无环

# ------------------ 测试 ------------------
if __name__ == "__main__":
    # 1) 无环链表：1 -> 2 -> 3 -> 4 -> None
    a = ListNode(1)
    b = ListNode(2)
    c = ListNode(3)
    d = ListNode(4)
    a.next = b
    b.next = c
    c.next = d
    print("无环链表有环？", has_cycle(a))   # False

    # 2) 有环链表：1 -> 2 -> 3 -> 4 ─┐
    #                    ↑__________┘
    a.next = b
    b.next = c
    c.next = d
    d.next = b                        # 制造环
    print("有环链表有环？", has_cycle(a))   # True