数组与字符串

数组是内存中连续的一段存储，字符串在多数语言里是"只读的字符数组"。它们是最基础的数据结构，也是面试笔试题的主力：前缀和、双指针、滑动窗口几乎都建立在数组与字符串之上，掌握它们的特性与套路非常划算。

数组的内存布局与特性

数组元素在内存中连续排列，每个元素大小相同，所以按下标访问只需一次地址计算：地址 = 基址 + 下标 × 元素大小，随机访问为 O(1)。

数组 arr[0..4]，每个元素 4 字节：
地址: 0x100 0x104 0x108 0x10C 0x110
元素: [ 10 ] [ 20 ] [ 30 ] [ 40 ] [ 50 ]

arr = [1, 2, 3, 4, 5]
print(arr[2])         # O(1) 随机访问，输出：3
arr.insert(0, 0)      # 头部插入 O(n)：后面元素整体右移
arr.append(6)         # 尾部追加平均 O(1)（摊还分析）
print(arr)            # 输出：[0, 1, 2, 3, 4, 5, 6]

代价是插入/删除需要搬移元素：头部插入删除为 O(n)，中间同样 O(n)。C 语言数组长度固定；Python list、Java ArrayList 是自动扩容的动态数组（扩容时整体搬迁，均摊后仍为 O(1)）。

字符串的特点

• Java/Python 中字符串不可变：每次拼接都会创建新对象，循环内 s += c 是 O(n²)，应改用 StringBuilder/join。
• C 语言字符串是 char[] 以 \0 结尾，可原地修改，但易越界。
• Go 字符串不可变，频繁拼接用 strings.Builder。

// Java：循环内拼接字符串的低效写法与正确写法（需放进 main 方法中运行）
String s = "";
for (int i = 0; i < 10000; i++) {
    s += i;                       // 每次循环都新建字符串，O(n²)
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10000; i++) {
    sb.append(i);                 // 可变缓冲，O(n)
}
String ok = sb.toString();

面试常考字符串的子串匹配（朴素 O(n·m) 与 KMP O(n+m)）、回文、字符频次统计；统计用固定 128 位或 26 位数组做哈希即可，不必上 HashMap。

前缀和：快速求区间和

预处理一次得到前缀和数组，之后任意区间 [i, j] 的和都能 O(1) 得到：

def prefix_sum(a):
    s = [0]
    for x in a:
        s.append(s[-1] + x)
    return s

s = prefix_sum([1, 2, 3, 4])
print(s)                     # 输出：[0, 1, 3, 6, 10]
# 区间 a[1..3] 的和 = s[4] - s[1] = 10 - 1 = 9

前缀和的进阶是差分数组（区间批量加减 O(1)）与二维前缀和（矩阵子块求和 O(1)），都是把多次查询从 O(n) 降到 O(1) 的经典手法。

双指针与滑动窗口

有序数组去重、两数之和、判断回文都可让两个指针相向或同向移动，把 O(n²) 暴力降为 O(n)：

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

print(is_palindrome("racecar"))   # 输出：True
print(is_palindrome("hello"))     # 输出：False

滑动窗口是"同向双指针"维护一段区间，配合哈希表可解"最长无重复子串""最小覆盖子串"等问题，每个元素至多进出窗口一次，整体 O(n)。

小结

数组的考点是"连续内存换来 O(1) 访问、付出 O(n) 插入删除"，字符串的考点是"不可变与拼接开销"。前缀和、双指针、滑动窗口三个套路吃透，大部分数组与字符串的笔试题都能从容应对。