数组与字符串

第 3 章 · 数据结构与算法

从最基础的开始。 数组和字符串是程序里最常见的数据形式：一排格子，按顺序放着一组同类型的数据。几乎每一种编程语言都内置它们，很多「高级」结构（列表、矩阵、哈希表里的桶）底层也离不开数组。这一章把线性存储、下标、切片讲清楚，再简单延伸几种常见套路——双指针、滑动窗口、前缀和——你在刷题和写业务时都会反复用到。

一、什么是数组

数组是在内存里连续存放的、同一类型的一组元素。每个元素有一个下标（索引），从 0 开始编号，所以第一个元素是下标 0，第二个是 1，依此类推。因为地址连续，只要知道首地址和每个元素占多少字节，就能用「首地址 + 下标 × 元素大小」直接算出第 i 个元素的地址，所以按下标访问是 O(1)。

数组：连续格子，下标从 0 开始，每个格子存一个元素

很多语言里数组长度固定（如 C/Java 的定长数组），有的语言提供「动态数组」（如 Python 的 list、C++ 的 vector）：长度可变，在末尾追加均摊 O(1)，在中间插入或删除需要把后面的元素整体移动，是 O(n)。

二、数组操作的复杂度

有了「连续存储 + 下标」这两点，就能直接推出常见操作的大 O：

操作	复杂度	说明
按下标访问 / 修改	O(1)	直接算地址
在末尾追加	O(1) 均摊	动态数组可能需扩容
在中间插入 / 删除	O(n)	后面元素整体移动
查找（未排序）	O(n)	只能顺序扫
查找（已排序）	O(log n)	二分

所以：数组适合「按下标随机访问」和「顺序遍历」；不适合频繁在中间插入删除，那种场景后面会学到链表更合适。

三、切片与区间

「取一段连续元素」非常常见，这就是切片（slice）或子数组。不同语言写法不同，但本质都是区间：

左闭右开 [l, r)：包含下标 l，不包含 r，长度为 r − l。Python、C++ STL、很多算法书都用这种，这样「空区间」可以写成 [i, i)，不会出现「负数长度」。
双闭 [l, r]：两端都包含，长度为 r − l + 1。有的语言或 API 用这种。

写代码和看题时一定要先看清题目用的是哪种区间，避免 off-by-one 错误。子数组、子串（字符串的一段）都对应一个区间，很多题就是在所有满足条件的区间里找最优。

在 Python 中，列表 list 即动态数组，切片为左闭右开 [l:r] 表示 [l, r)：

# 类型标注需 from __future__ import annotations 或 typing
from typing import List

def example_slice(a: List[int], l: int, r: int) -> List[int]:
    """子数组 [l, r)，即 a[l:r]。"""
    return a[l:r]

# 例：a = [3, 7, 2, 9, 1, 5, 8, 4]，a[2:5] = [2, 9, 1]

四、字符串：字符的「数组」

字符串可以看成字符组成的序列，在很多语言里支持像数组一样按下标访问（如 s[0]、s[i]）。有的语言里字符串是不可变的（如 Python、Java）：「改一个字符」实际是生成新字符串，复杂度 O(n)；有的支持原地修改（如 C 的字符数组）。

字符串 "hello"：按下标 0～4 访问每个字符

常见操作：比较（字典序）、拼接（注意不可变时会产生新串）、子串（即区间 [l, r) 或 [l, r]）、查找子串/字符（暴力 O(n·m)，更快的有 KMP 等，后续可单独学）。很多「数组题」的做法可以直接用在字符串上（如双指针判断回文、滑动窗口找最长不重复子串）。

五、常见应用延伸

下面三种套路在数组和字符串题里出现频率很高，先建立印象，后面做题时会反复用到。

1. 双指针（对撞 / 快慢）

用两个下标 left、right 同时遍历或从两端向中间移动，在 O(n) 内完成「找两个数」「去重」「判断回文」等。对撞：左指针从左、右指针从右，根据当前和或大小决定移动哪一边。快慢：快指针一次走两步、慢指针一步，用于找中点、判环等。

对撞双指针：L 从左、R 从右，向中间移动

2. 滑动窗口

维护一个连续区间 [l, r]，根据题目条件移动左边界或右边界，在 O(n) 内枚举所有「满足条件的子数组/子串」或求最长/最短的一段。典型题：最长不重复子串、和为 target 的连续子数组、最小覆盖子串。

3. 前缀和

预处理出 pre[i] = a[0] + a[1] + … + a[i-1]，则区间 [l, r) 的和 = pre[r] - pre[l]，一次 O(1) 查询。适合「多次询问区间和」的场景。

六、例题与代码详解

下面三道题分别对应双指针、滑动窗口、前缀和，给出完整题目描述、Python3 解法（带类型标注）与详细讲解。

例题 1：两数之和 II（有序数组）

题目描述：给定一个非递减整数数组 numbers 和一个目标值 target，在数组中找两个不同的数，使它们的和等于 target。返回这两个数的下标（从 1 开始）。题目保证有且仅有一组解。

输入：numbers 长度 ≥ 2，元素非递减；target 为整数。
输出：长度为 2 的列表 [i, j]，满足 1 ≤ i < j 且 numbers[i-1] + numbers[j-1] == target。

from typing import List

def two_sum_sorted(numbers: List[int], target: int) -> List[int]:
    """对撞双指针：左端 + 右端，和大了就缩小右，和小了就扩大左。"""
    left: int = 0
    right: int = len(numbers) - 1
    while left < right:
        total: int = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]  # 题目要求下标从 1 开始
        if total > target:
            right -= 1
        else:
            left += 1
    return []  # 题目保证有解，不会走到这里

讲解：因为数组有序，左小右大。若 numbers[left] + numbers[right] > target，则任意以当前 left 为左、更靠右的数和 numbers[right] 之和只会更大，所以只能 right -= 1；同理若和小于 target 则 left += 1。每轮要么 left 加一要么 right 减一，不会漏解。时间复杂度 O(n)，空间 O(1)。

例题 2：无重复字符的最长子串

题目描述：给定字符串 s，求其中不含有重复字符的最长子串的长度。

输入：s 由英文字母、数字、符号、空格组成。
输出：一个整数，即最长无重复子串的长度。

def length_of_longest_substring(s: str) -> int:
    """滑动窗口：窗口 [left, right] 内无重复，用 set 记录窗口内字符。"""
    seen: set[str] = set()
    left: int = 0
    best: int = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.discard(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

讲解：维护窗口 [left, right]，保证窗口内无重复字符。右指针 right 每次右移一位；若 s[right] 已在窗口内（在 seen 中），则不断左移 left 并从 seen 中移除对应字符，直到 s[right] 不再在 seen 中，再把 s[right] 加入 seen。每次更新 best 为当前窗口长度与历史最大值的较大者。每个字符最多进、出 seen 各一次，时间复杂度 O(n)，空间 O(min(n, 字符集大小))。

例题 3：区域和检索（前缀和）

题目描述：给定整数数组 nums，实现类 NumArray，支持：
① 构造时用 nums 初始化；
② sum_range(left, right) 返回 nums[left] + nums[left+1] + … + nums[right]（闭区间 [left, right]）。

输入：构造时 nums；查询时 0 ≤ left ≤ right < len(nums)。
输出：sum_range 返回区间和。

from typing import List

class NumArray:
    """前缀和：pre[i] = nums[0]+...+nums[i-1]，则 [left, right] 和 = pre[right+1]-pre[left]。"""

    def __init__(self, nums: List[int]) -> None:
        n: int = len(nums)
        self.pre: List[int] = [0] * (n + 1)
        for i in range(n):
            self.pre[i + 1] = self.pre[i] + nums[i]

    def sum_range(self, left: int, right: int) -> int:
        return self.pre[right + 1] - self.pre[left]

讲解：pre[i] 表示前 i 个元素的和（即 nums[0..i-1]）。闭区间 [left, right] 的和等于前 right+1 项和减去前 left 项和，即 pre[right+1] - pre[left]。构造时 O(n) 预处理，每次查询 O(1)。

小贴士： 数组题很多都是「枚举子数组/子串」或「在有序数组上二分/双指针」。先想清楚要枚举什么、用什么数据结构维护当前状态，再套双指针、滑动窗口或前缀和，往往就能把暴力 O(n²) 或 O(n³) 压成 O(n) 或 O(n log n)。

七、小结

数组是连续存储、下标从 0 开始的线性结构，随机访问 O(1)，中间插入删除 O(n)。切片/区间要区分左闭右开 [l, r) 和双闭 [l, r]。字符串可视为字符序列，支持下标访问和子串操作。常见套路：双指针（对撞/快慢）做两数之和、去重、回文；滑动窗口做最长不重复子串、区间和满足条件；前缀和做多次区间和查询。下一章我们会学链表：不连续存储，用指针串起来，插入删除只需改指针，但失去 O(1) 随机访问。