双指针和滑动窗口：数组和字符串优化技巧

1. 概述

当遇到遍历数组或字符串的问题，而暴力解法的时间复杂度为 O(n²) 或 O(n³) 时，两种技巧——双指针和滑动窗口——通常能帮助你将复杂度降低到 O(n)。本文解释这两种技巧的核心思想，并附上具体的 Java 示例：已排序数组中的两数之和、回文检查、固定窗口内的最大子数组和，以及最长不重复字符子串。读完后，你将认识到这些模式，并能将其应用于许多类似的问题。

2. 什么是双指针

双指针是一种技巧，使用两个索引变量（指针）在数据结构（通常是已排序的数组或字符串）上移动，以避免嵌套循环。两个指针可以按以下方式移动：

• 同向（快/慢）：用于删除重复元素、检测循环。
• 相向（从两端的左/右）：用于查找和等于目标值的配对、检查回文。

2.1. 双指针相向：找和等于目标的配对

经典问题：给定一个递增排序的数组，找两个数，其和等于目标值。

public class TwoSumSorted {

    public int[] findPair(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{numbers[left], numbers[right]};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
}

解释：

• left 从数组开头开始，right 从末尾开始。
• 如果 sum < target，左边的数太小，因此增加 left 以获取更大的数。
• 如果 sum > target，右边的数太大，因此减少 right。
• 循环最多运行 n 步，因为每次迭代 left 或 right 都会移动一位，时间复杂度为 O(n)，而不是两层循环的 O(n²)。

使用 JUnit 5 + AssertJ 测试：

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.10.2</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.25.3</version>
    <scope>test</scope>
</dependency>

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class TwoSumSortedTest {

    private final TwoSumSorted twoSum = new TwoSumSorted();

    @Test
    void shouldFindPairWhenSumMatchesTarget() {
        int[] numbers = {1, 3, 5, 8, 11};

        int[] result = twoSum.findPair(numbers, 13);

        assertThat(result).containsExactly(5, 8);
    }
}

注意： 这种技巧要求数组已排序。如果数组未排序，你需要先排序（O(n log n)），或使用 HashMap 来保持 O(n) 时间复杂度且无需排序。

2.2. 双指针检查回文

public class PalindromeChecker {

    public boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

两个指针分别从字符串的两端开始，比较字符并向中间移动。如果遇到不相同的字符，立即返回 false——无需遍历到底。这就是为什么这种技巧比反转字符串后比较要快，因为它避免了创建中间 StringBuilder 对象。

3. 什么是滑动窗口

滑动窗口是双指针的一种变体，应用于涉及连续子序列（subarray/substring）的问题。与其每次从头计算，不如维护一个“窗口” [left, right] 并在窗口滑动时逐步更新，重用之前计算的结果。

有两种类型：

• 固定大小窗口：窗口大小固定（例如 k 个元素）。
• 可变大小窗口：窗口大小根据题目条件伸缩。

3.1. 固定大小窗口：大小为 k 的最大子数组和

public class MaxSumSubarray {

    public int maxSum(int[] numbers, int windowSize) {
        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += numbers[i];
        }

        int maxSum = windowSum;
        for (int right = windowSize; right < numbers.length; right++) {
            windowSum += numbers[right] - numbers[right - windowSize];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

解释：

• 第一个循环计算第一个窗口的和（从索引 0 到 windowSize - 1）。
• 之后，每次向右移动窗口一步：加入新元素（numbers[right]），减去离开窗口的元素（numbers[right - windowSize]）。
• 因此，每步只需 O(1)，而不是重新计算 k 个元素的和，总时间复杂度为 O(n)。

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class MaxSumSubarrayTest {

    private final MaxSumSubarray solver = new MaxSumSubarray();

    @Test
    void shouldReturnMaxSumOfWindowSizeThree() {
        int[] numbers = {2, 1, 5, 1, 3, 2};

        int result = solver.maxSum(numbers, 3);

        assertThat(result).isEqualTo(9); // 窗口 [5, 1, 3]
    }
}

3.2. 可变大小窗口：最长不重复字符子串

这道题中窗口根据“不存在重复字符”的条件伸缩。

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public int lengthOfLongestSubstring(String text) {
        Map<Character, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < text.length(); right++) {
            char current = text.charAt(right);
            if (lastSeenIndex.containsKey(current) && lastSeenIndex.get(current) >= left) {
                left = lastSeenIndex.get(current) + 1;
            }
            lastSeenIndex.put(current, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

解释：

• right 始终向前移动（扩大窗口），left 只在遇到窗口内的重复字符时跳动。
• lastSeenIndex 记录每个字符最近出现的位置，以确定 left 应该跳到哪里。
• 条件 lastSeenIndex.get(current) >= left 确保只有当该字符仍在当前窗口内时，才算作重复，避免 left 错误地向后跳。
• 每个字符仅在 right 处被处理一次，因此总时间复杂度为 O(n)。

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class LongestUniqueSubstringTest {

    private final LongestUniqueSubstring solver = new LongestUniqueSubstring();

    @Test
    void shouldReturnLengthOfLongestUniqueSubstring() {
        int result = solver.lengthOfLongestSubstring("abcabcbb");

        assertThat(result).isEqualTo(3); // "abc"
    }

    @Test
    void shouldHandleAllSameCharacters() {
        int result = solver.lengthOfLongestSubstring("bbbbb");

        assertThat(result).isEqualTo(1);
    }
}

手动调试 "abcabcbb" 的输出：

right=0 'a' -> 窗口="a"    长度=1
right=1 'b' -> 窗口="ab"   长度=2
right=2 'c' -> 窗口="abc"  长度=3
right=3 'a' -> 重复，left=1 -> 窗口="bca" 长度=3
right=4 'b' -> 重复，left=2 -> 窗口="cab" 长度=3
...
maxLength = 3

4. 对比和何时使用各种技巧

场景	适用技巧
已排序数组，查找满足和条件的配对/三元组	双指针相向
检查对称性（回文）、原地反转数组	双指针相向
删除已排序数组中的重复元素	双指针同向（快/慢）
大小为 k 的固定子数组/子字符串	滑动窗口（固定大小）
满足动态条件的子数组/子字符串（无重复、和 ≤ 目标等）	滑动窗口（可变大小）

共同点：两种技巧都避免重新计算已处理的部分，通过在指针/窗口移动时维护状态（和、集合、映射），从而将复杂度从 O(n²) 降低到 O(n)。

5. 常见错误

• 忘记停止条件 left < right：容易导致无限循环或在 left == right 时比较元素与自身。
• 对未排序的数组应用双指针而忘记先排序——结果完全错误，因为指针增减逻辑依赖于数组的单调性。
• 在滑动窗口中，当 left 移动时忘记更新状态：例如忘记从 HashMap/sum 中删除旧元素，导致窗口记住已不属于窗口的数据。
• 混淆窗口扩展/收缩的条件：需要明确哪个条件使 right 前进，哪个条件使 left 前进——如果搞反了，窗口永远无法正确收缩。

注意： 这两种技巧不适合当问题要求检查所有非连续的子集合时（例如子集和）——此时需要回溯或动态规划，不是滑动窗口。

6. 结论

双指针和滑动窗口是解决时间复杂度为线性的数组/字符串问题的两个基础工具。识别模式——已排序数组需要查找配对，或连续子数组/子字符串需要优化——帮助你选择正确的技巧，并编写简洁、易测试的代码，如上面的示例。练习时，尽量自己画出状态逐步进行，以理解清楚不变量，在编码前打好基础。