双指针思想（理论总结）

双指针是处理数组/字符串问题最常见的技巧。核心思想是：

用两个索引同时移动，减少重复计算，从而提高效率。

常见的三种模式：

快慢指针（Floyd 思想）

定义：一个指针移动快，一个移动慢。
核心套路：快指针一次走两步，慢指针一次走一步；或者慢指针维护有效区间，快指针扫描寻找新值。
典型应用：
1. 链表是否有环（快指针追上慢指针 → 有环）
2. 链表中点（快指针一次两步，慢指针一步 → 快到头时，慢指针在中点）
3. 删除重复元素（慢指针指向“有效区间尾部”，快指针遍历寻找新元素）
时间复杂度：O(n)，空间 O(1)。

快慢相遇找环，中点快慢分担，去重靠快慢分工。

LeetCode 141. 环形链表

模式：快慢指针
条件：while fast and fats.next
判定
- 相遇：有环
- 到 null：无环
复杂度
- 时间O(N)
- 空间O(1)

class Solution:
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

LeetCode 142. 环形链表 II

见 LeetCode 141. 环形链表使用快慢指针，若相遇则说明有环。
证明如何找入口
- 假设：
  - 链表头到环入口的距离为 a
  - 环入口到第一次相遇点的距离为 b
  - 环的长度为 c
- 慢指针走的路：a + b
- 快指针走的路：a + b + k*c
- 因为快指针速度为慢指针的两倍：
  - 2(a + b) = a + b + k*c
  - 即 a = k*c - b
- 也就是说：
  - 从头走 a 步可以到入口
  - 从相遇点走 c - b 步也能到入口
实现方法
- 当快慢指针第一次相遇的时候，把其中的一个指针放回 head，另一个留在相遇点
- 然后两个都改成一次走一步，再次相遇就是环的入口

class Solution:
    def detectCycle(self, head):
        slow = fast = head
        
        # 1. 判环
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        else:
            return None   # 无环
        
        # 2. 找入口
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow

LeetCode 876. 链表的中间节点

模式：快慢指针
应用：链表找中点
写法：
- 偶数时返回第二个中点: while fast and fast.next
- 偶数时返回第一个中点: while fast.next and fast.next.next
特点：自动处理奇偶情况，返回第二个中点

class Solution:
    def middleNode(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

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

模式：快慢指针
应用：有序数组去重
写法：慢指针维护“有效区间尾部”，快指针遍历
复杂度：O(n) / O(1)

class Solution:
    def removeDuplicates(self, nums):
        if not nums:
            return 0
        
        slow = 0
        for fast in range(1, len(nums)):
            if nums[fast] != nums[slow]:
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1

循环要从 fast = 1 开始，因为初始 slow = 0 已经指向第一个元素。
最后返回 slow + 1，因为 slow 指的是最后一个有效元素的下标。

总结

有环 → 相遇

入口 → 再次相遇

点 → 快到头，慢在中点

去重 → 慢指针存结果，快指针找新值

左右夹逼（Two Ends / Two Sum）

定义：两个指针分别从数组两端向中间靠拢。
核心套路：
- 设置两个指针，left 从头开始，right 从尾开始
- 根据题目条件，逐步向中间移动：
  - 如果结果太大，右指针左移
  - 如果结果太小，左指针右移
- 保证整个过程 O(N)，而不是 0(N^2)
典型应用：
1. 有序数组两数之和（如果和太大 → 右指针左移；和太小 → 左指针右移）
2. 盛最多水的容器（移动高度较小的一端，尝试更大面积）
3. 三数之和（固定一个数，剩下两个数用双指针搜索）
时间复杂度：O(n) 或 O(n²)，比暴力 O(n²) / O(n³) 更快。
易错点：一定要保证数组有序，如果无序，需要先排序

LeetCode 167. 两数之和 II（有序数组）

模式：左右夹逼
应用：有序数组 two sum
移动规则
- 和小：左指针右移
- 和大：右指针左移
复杂度：O(N)/O(1)

class Solution:
    def twoSum(self, numbers, target):
        left, right = 0, len(numbers) - 1
        while left < right:
            s = numbers[left] + numbers[right]
            if s == target:
                return [left + 1, right + 1]
            elif s < target:
                left += 1
            else:
                right -= 1

LeetCode 11. 盛最多水的容器

模式：左右夹逼
应用：最大面积（盛水容器）
公式：面积 = (right - left) * min(height[left], height[right])
移动规则：短板效应 -> 移动高度较小的一侧

class Solution:
    def maxArea(self, height):
        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:
            h = min(height[left], height[right])
            area = h * (right - left)
            max_area = max(area, max_area)
            
            # 移动短板
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

LeetCode 15. 三数之和

模式：排序 + 左右夹逼
应用：三数之和（和为0的三元组）
步骤：
- 排序
- 固定一个数
- 双指针去搜索另外两个数
- 去重处理
复杂度：O(N^2)

滑动窗口（Sliding Window）

定义：用两个指针维护一个区间 [l, r]，右指针不断扩展，左指针在不满足条件时收缩。
典型应用：
1. 最长无重复子串（当区间内有重复字符时，左指针右移缩小窗口）
2. 最小覆盖子串（右指针扩展直到满足条件，再收缩左指针优化答案）
3. 子数组和问题（如找到和大于 K 的最短子数组）
时间复杂度：O(n)，因为左右指针最多各移动 n 次。

小结（笔记模板示范）

题型：双指针
套路：两个索引协同移动，减少重复计算
三大模式：

快慢指针 → 判断环 / 找中点
左右夹逼 → 有序数组求和 / 盛水容器
滑动窗口 → 子串/子数组问题