两个指针和滑动窗口 - AI如何高效扫描数据

为什么智能扫描很重要

想象一下，人工智能正在监视实时视频以发现可疑活动。它无法每秒重新观看整个录音 - 它需要在流中滑动一个注意力窗口，仅跟踪足够的上下文。这正是两个指针和滑动窗口模式对顺序数据所做的事情。

这两种技术都将强力 O(n²) 扫描转变为优雅的 O(n) 传递。

两指针技术

将两个参考放入一个序列中并根据规则移动它们。主要有两种口味。

收敛指针

从两端开始一个指针并向内移动。非常适合排序数据。

**经典问题 - 对和：**给定一个排序数组，找到两个与目标相加的数字。

function pairSum(arr, target):
    left = 0
    right = arr.length - 1
    while left < right:
        sum = arr[left] + arr[right]
        if sum == target: return (left, right)
        if sum < target: left += 1
        else: right -= 1
    return null

因为数组已排序，所以向右移动 left 会增加总和，向左移动 right 会减少总和 - 确保我们永远不会错过有效的对。

同向指针

两个指针都向前移动，但速度不同。对于分区或循环检测很有用。

示例 - 就地删除重复项： 慢速指针标记写入位置；快速指针向前扫描。

function removeDuplicates(arr):
    slow = 0
    for fast in 1..arr.length - 1:
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1

滑动窗口模式

滑动窗口维护大小为_k_（固定）或可变长度的连续子序列，增量更新聚合而不是从头开始重新计算。

固定大小的窗口

在数组中滑动恰好包含 k 个元素的窗口。

示例 - 任意 k 个连续元素的最大总和：

function maxSubarraySum(arr, k):
    windowSum = sum(arr[0..k-1])
    best = windowSum
    for i in k..arr.length - 1:
        windowSum += arr[i] - arr[i - k]
        best = max(best, windowSum)
    return best

每一步都会添加进入窗口的新元素并减去离开的元素 - 每次移动 O(1)。

可变大小的窗口

扩大窗口以包含更多数据，然后在违反约束时缩小窗口。

示例 - 没有重复字符的最长子字符串：

function longestUnique(s):
    seen = {}
    left = 0
    best = 0
    for right in 0..s.length - 1:
        if s[right] in seen and seen[s[right]] >= left:
            left = seen[s[right]] + 1
        seen[s[right]] = right
        best = max(best, right - left + 1)
    return best