13 min read2,524 words

数组与字符串核心操作

简介

数组与字符串是算法与数据结构中最基础、最核心的两种线性结构，它们是解决绝大多数编程问题的起点。数组提供了一种在连续内存空间中存储相同类型元素的方式，其高效的随机访问特性是构建更复杂数据结构（如哈希表、堆）的基石。字符串则可以视为字符的数组，但在许多高级语言中，它被设计为不可变对象，这一特性深刻影响了其操作方式和性能表现。

掌握数组与字符串的核心操作，不仅仅是学会如何遍历、修改元素，更重要的是理解其背后的内存模型，并能够运用高效的算法模式来解决实际问题。其中，双指针技巧是处理数组和字符串问题的“瑞士军刀”，它通过巧妙地使用两个或多个指针协同遍历，能够在单次循环中完成看似复杂的任务，将时间复杂度从 O(n²) 降低到 O(n)。本章将深入剖析数组的内存布局、字符串的不可变性，并重点讲解对撞指针与快慢指针这两种经典的双指针模式，最后通过精选的 LeetCode 例题来巩固这些核心概念。

核心概念

数组的内存模型与基本操作

在计算机内存中，数组被分配在一块连续的地址空间中。数组名（或引用）本身存储的是数组首元素的内存地址。由于元素类型相同，每个元素占用的字节大小固定，因此可以通过一个简单的公式进行随机访问：元素地址 = 基地址 + 索引 * 元素大小。这使得通过下标访问任意元素的时间复杂度为 O(1)。

数组的基本操作包括： - 查：通过索引直接访问，时间复杂度 O(1)。 - 改：通过索引找到元素后修改其值，时间复杂度 O(1)。 - 增：在数组末尾添加元素（如果空间足够）为 O(1)；在数组中间或开头插入元素，需要将后续元素全部后移，最坏情况为 O(n)。 - 删：删除数组末尾元素为 O(1)；删除中间或开头的元素，需要将后续元素全部前移，最坏情况为 O(n)。

字符串的不可变性与常用操作

在许多现代编程语言（如 Python、Java、C#）中，字符串被设计为不可变对象。这意味着一旦一个字符串被创建，它的内容就不能被改变。任何看似修改字符串的操作（如拼接、替换），实际上都是创建了一个全新的字符串对象。这一特性带来了线程安全、简化设计等优点，但也意味着频繁修改字符串的操作（如在循环中拼接）会产生大量临时对象，性能开销较大。

字符串的常用操作包括： - 切片：获取原字符串的一个子串。在支持切片语法的语言中（如 Python），这是一个 O(k) 的操作（k 为子串长度），通常通过创建新字符串实现。 - 拼接：将多个字符串连接成一个新字符串。使用 join 方法（如 Python 的 str.join(list)）通常比循环中使用 + 运算符更高效。 - 查找：判断一个子串是否存在于字符串中，常用算法有暴力匹配、KMP 等。

双指针技巧的引入

双指针技巧是优化数组和字符串遍历过程的核心思想。它使用两个指针（通常是索引变量）在序列上以不同的策略移动，从而在一次遍历中完成特定任务。主要分为两种模式：

对撞指针：两个指针分别指向序列的首尾，并向中间移动，直到它们相遇或满足某个条件。常用于有序数组的查找、判断回文等问题。
快慢指针：两个指针从同一端开始，但移动步长不同（例如，快指针每次移动两步，慢指针移动一步）。常用于检测循环（如链表中的环）、寻找中点、移除特定元素等问题。

下面的 Mermaid 图展示了双指针的两种基本工作模式：

实战示例

下面我们通过一个经典的“移除元素”问题来演示快慢指针的实战应用。题目要求：给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。元素的顺序可以改变。

快慢指针解法思路： - 定义慢指针 slow，指向下一个待赋值的位置。 - 定义快指针 fast，用于遍历整个数组。 - 遍历时，如果 nums[fast] 不等于目标值 val，就将其赋值给 nums[slow]，然后 slow 前进一步。 - 最终，slow 索引的位置就是新数组的长度，nums[0:slow] 即为移除目标值后的数组。

def removeElement(nums, val):
"""
使用快慢指针原地移除数组中所有等于 val 的元素。
:type nums: List[int]
:type val: int
:rtype: int
"""
# 初始化慢指针 slow，它指向下一个“有效”元素应该存放的位置
slow = 0
# 快指针 fast 用于遍历整个数组
for fast in range(len(nums)):
# 如果当前快指针指向的元素不是要删除的目标值
if nums[fast] != val:
# 将该元素复制到慢指针指向的位置
nums[slow] = nums[fast]
# 慢指针向前移动一位，为下一个有效元素预留位置
slow += 1
# 循环结束后，slow 的值即为新数组的长度
return slow
# 示例运行
if __name__ == "__main__":
# 测试用例1
nums1 = [3, 2, 2, 3]
val1 = 3
new_length1 = removeElement(nums1, val1)
print(f"数组: {nums1[:new_length1]}")  # 输出: [2, 2]
print(f"新长度: {new_length1}")        # 输出: 2
# 测试用例2
nums2 = [0, 1, 2, 2, 3, 0, 4, 2]
val2 = 2
new_length2 = removeElement(nums2, val2)
print(f"数组: {nums2[:new_length2]}")  # 输出: [0, 1, 3, 0, 4]
print(f"新长度: {new_length2}")        # 输出: 5

对比分析

在解决数组和字符串问题时，根据数据特性和问题要求，选择不同的指针策略至关重要。下表对比了两种主要双指针模式及其变体的特点：

方案	优势	劣势	适用场景
对撞指针	逻辑直观，通常只需一次遍历。在有序数组中能高效缩小搜索范围。	通常要求输入数据有序，或者问题本身具有对称性（如回文）。	有序数组的两数之和、三数之和问题；验证回文字符串；反转字符串中的元音字母。
快慢指针	不依赖数据有序性，适用于单链表等只能单向遍历的结构。能原地修改数组。	指针移动逻辑有时较复杂，需要仔细处理边界条件。	原地移除数组中的特定元素；寻找链表的中点；判断链表是否有环；寻找重复数（Floyd判圈算法）。
滑动窗口 (双指针变体)	能高效解决子串/子数组的连续区间问题，将暴力法的 O(n²) 优化为 O(n)。	需要维护窗口状态（如哈希表、计数器），实现细节较多。	寻找无重复字符的最长子串；长度最小的子数组；字符串的排列检查。
分离指针 (多序列)	能并行遍历多个数组或字符串，处理归并、比较类问题。	需要处理不同序列长度不一致的情况。	合并两个有序数组；最长公共前缀；判断子序列。

最佳实践

优先考虑原地操作：对于数组问题，在题目允许的情况下，优先考虑像“快慢指针”这样的原地算法，避免使用额外的 O(n) 空间。这不仅节省内存，也常常是题目的核心考察点。
利用语言特性，但理解其成本：例如在 Python 中处理字符串，知道 s[::-1] 可以快速反转，但也要明白这会创建一个新字符串。在需要频繁拼接时，应使用 list 存储字符片段，最后用 ''.join(list) 一次成型，这比循环中使用 += 高效得多。
画图分析指针移动：在解决复杂的双指针问题时，不要空想。在纸上或注释中画出数组和指针的初始状态、中间状态和最终状态，能极大地帮助理清逻辑，避免差一错误（Off-by-one error）。
先思考暴力法，再优化：面对新问题时，先思考一个简单但可能低效的暴力解法。这能帮助你彻底理解问题。然后分析暴力解法中重复或低效的部分，这往往是引入双指针等优化技巧的切入点。
注意边界条件和循环不变式：双指针算法的正确性依赖于循环中指针移动的规则。明确循环开始时、每次迭代后、循环结束时，指针所代表的意义（循环不变式），并仔细处理数组为空、指针越界等边界情况。

小结

本章深入探讨了数组与字符串这两大基础数据结构的核心。数组的连续内存模型支持 O(1) 的随机访问，但中间位置的插入删除成本较高；字符串的不可变性则要求我们在操作时特别注意性能。双指针技巧，特别是对撞指针和快慢指针，是提升线性结构问题解决效率的强大工具，它们能将许多问题的复杂度从 O(n²) 降至 O(n)。通过“移除元素”、“反转字符串”、“最长公共前缀”等例题的实践，我们应掌握根据问题特征选择合适指针模式的能力，并养成画图分析、注意边界条件的良好习惯。

下一节：链表：单链表、双链表与虚拟头节点