数据结构

什么是“数据结构”？数据结构是计算机用来组织、存储和管理数据的方式。简单说，它回答的是一个问题：数据应该怎样摆放，才能更方便、更高效地使用？在程序中，我们不仅要“保存数据”，还要经常对数据进行操作，例如：查找某个元素；插入新数据；删除旧数据；修改数据；遍历全部数据；按某种规则排序或关联数据。不同的数据结构，适合不同的操作场景。选对数据结构，程序可能非常高效；选错数据结构，程序可

在不进行网络搜索，不使用外部工具的情况下，你对自己最自信的知识领域是哪些？

数组

数组的“奇技淫巧”：本质是利用连续性和下标

数组最大的特点是：元素按顺序存放，可以通过下标快速访问。所以很多数组技巧，本质上都是在利用：

下标可以直接定位；
元素有固定顺序；
可以从左到右、从右到左扫描；
可以把数组本身当作“状态表”或“映射表”。

下面介绍一些常见又很实用的数组技巧。

1. 双指针：两个下标配合移动

双指针是数组题里最常见的技巧之一。它通常用两个变量表示位置，例如 left 和 right。

常见场景

反转数组；
删除重复元素；
判断回文；
有序数组中找两数之和；
原地移动元素。

例如，反转数组：

python

nums = [1, 2, 3, 4, 5]
left, right = 0, len(nums) - 1
while left < right:    nums[left], nums[right] = nums[right], nums[left]    left += 1    right -= 1
print(nums)  # [5, 4, 3, 2, 1]

nums = [1, 2, 3, 4, 5]
left, right = 0, len(nums) - 1
while left < right:    nums[left], nums[right] = nums[right], nums[left]    left += 1    right -= 1
print(nums)  # [5, 4, 3, 2, 1]

这个技巧的好处是：不需要额外数组，空间复杂度是 $O(1)$ 。

2. 快慢指针：原地过滤数组

快慢指针是双指针的一种变体。

fast 负责遍历所有元素；
slow 负责记录“有效元素应该放在哪里”。

例如：删除数组中的某个值。

python

nums = [3, 2, 2, 3, 4]val = 3
slow = 0for fast in range(len(nums)):    if nums[fast] != val:        nums[slow] = nums[fast]        slow += 1
print(nums[:slow])  # [2, 2, 4]

nums = [3, 2, 2, 3, 4]val = 3
slow = 0for fast in range(len(nums)):    if nums[fast] != val:        nums[slow] = nums[fast]        slow += 1
print(nums[:slow])  # [2, 2, 4]

这里并没有真正删除元素，而是把需要保留的元素移动到前面。很多语言中的数组删除中间元素很慢，因为后面的元素要整体移动。快慢指针可以把多次移动优化成一次遍历。

3. 前缀和：快速求区间总和

如果你经常需要求数组某一段的和，例如 nums[l] 到 nums[r]，每次循环累加会比较慢。

可以提前构造一个前缀和数组。

python

nums = [2, 4, 1, 7, 3]
prefix = [0]for x in nums:    prefix.append(prefix[-1] + x)
# 求 nums[1] 到 nums[3] 的和：4 + 1 + 7l, r = 1, 3answer = prefix[r + 1] - prefix[l]
print(answer)  # 12

nums = [2, 4, 1, 7, 3]
prefix = [0]for x in nums:    prefix.append(prefix[-1] + x)
# 求 nums[1] 到 nums[3] 的和：4 + 1 + 7l, r = 1, 3answer = prefix[r + 1] - prefix[l]
print(answer)  # 12

前缀和的核心公式是：

sum(l, r) = prefix[r + 1] - prefix[l]

适合场景：

多次查询区间和；
统计子数组和；
二维矩阵区域求和；
配合哈希表解决“和为 K 的子数组”。

4. 差分数组：批量区间修改

前缀和适合“快速查询”，而差分数组适合“快速修改区间”。

假设你要对数组某个区间 [l, r] 都加上一个值，如果直接遍历区间，可能很慢。差分数组可以做到每次区间修改只改两个位置。

python

n = 5diff = [0] * (n + 1)
# 给区间 [1, 3] 加 10l, r, val = 1, 3, 10diff[l] += valdiff[r + 1] -= val
# 还原最终数组nums = [0] * ncurrent = 0for i in range(n):    current += diff[i]    nums[i] = current
print(nums)  # [0, 10, 10, 10, 0]

n = 5diff = [0] * (n + 1)
# 给区间 [1, 3] 加 10l, r, val = 1, 3, 10diff[l] += valdiff[r + 1] -= val
# 还原最终数组nums = [0] * ncurrent = 0for i in range(n):    current += diff[i]    nums[i] = current
print(nums)  # [0, 10, 10, 10, 0]

它的思想是：只记录变化从哪里开始，在哪里结束。

5. 滑动窗口：维护一段连续区间

滑动窗口常用于处理“连续子数组”或“连续子串”。

它通常有两个边界：

left：窗口左边界；
right：窗口右边界。

例如，求长度为 k 的连续子数组最大和：

python

nums = [1, 3, 2, 6, 4]k = 3
window_sum = sum(nums[:k])answer = window_sum
for right in range(k, len(nums)):    window_sum += nums[right]    window_sum -= nums[right - k]    answer = max(answer, window_sum)
print(answer)  # 12，对应 [2, 6, 4]

nums = [1, 3, 2, 6, 4]k = 3
window_sum = sum(nums[:k])answer = window_sum
for right in range(k, len(nums)):    window_sum += nums[right]    window_sum -= nums[right - k]    answer = max(answer, window_sum)
print(answer)  # 12，对应 [2, 6, 4]

滑动窗口的关键是：窗口右移时，加入新元素，移除旧元素，不用每次重新计算。

6. 原地哈希：把数组当作标记表

有时候数组元素范围有限，可以利用数组下标做映射。

例如，判断数字是否出现过：

python

nums = [2, 3, 1, 2]seen = [False] * 5
for x in nums:    if seen[x]:        print("重复数字:", x)        break    seen[x] = True

nums = [2, 3, 1, 2]seen = [False] * 5
for x in nums:    if seen[x]:        print("重复数字:", x)        break    seen[x] = True

如果题目限制数字范围是 1 到 n，甚至可以把原数组本身当作标记空间。不过这种技巧要小心，因为它会修改原数组。

7. 哨兵技巧：减少边界判断

有些算法中，边界判断很多，可以加一个“哨兵”元素简化逻辑。

例如找最小值时，可以预设一个极大值：

python

nums = [5, 2, 8, 1]
min_value = float("inf")
for x in nums:    if x < min_value:        min_value = x
print(min_value)  # 1

nums = [5, 2, 8, 1]
min_value = float("inf")
for x in nums:    if x < min_value:        min_value = x
print(min_value)  # 1

float("inf") 就像一个无穷大的哨兵，任何正常数字都比它小。

8. 排序后再处理：降低问题难度

很多数组问题，一旦排序，就会变得简单。

例如：

找重复元素；
合并区间；
双指针找两数之和；
贪心选择；
统计频率。

不过排序通常需要：

O(n \log n)

所以要权衡：排序能简化逻辑，但也会增加时间成本，并且可能改变原数组顺序。

总结：数组技巧可以继续深入这些方向

如果你想继续钻研数组，可以重点学习：

双指针
快慢指针
前缀和
差分数组
滑动窗口
二分查找
原地修改
排序 + 贪心
数组模拟栈和队列

数组看起来简单，但它是很多高级数据结构和算法的基础。真正的“奇技淫巧”不是死记模板，而是理解：下标、顺序、连续区间、状态映射这几个核心思想。