面试数据结构：数组与动态数组

数组是最基础的数据结构，特点是连续内存和随机访问。

复杂度

• 按下标访问：O(1)。
• 中间插入删除：O(n)。
• 末尾追加：动态数组均摊 O(1)。

vector 扩容

std::vector 容量不足时会分配更大的连续空间，并移动旧元素。

std::vector<int> v;
v.reserve(1000);

如果提前知道规模，reserve 可以减少扩容次数。

面试重点

数组题通常考察双指针、前缀和、滑动窗口和原地修改。

为什么数组题出现频率高

数组是最容易构造测试数据的数据结构，也是最容易考察边界意识的题型。比如“删除有序数组中的重复项”，看起来只是移动元素，实际考察的是读写指针是否能保持正确不变量。

双指针模板

int slow = 0;
for (int fast = 0; fast < nums.size(); ++fast) {
    if (should_keep(nums[fast])) {
        nums[slow++] = nums[fast];
    }
}

fast 负责扫描原数组，slow 负责维护有效区间。这个模板可以用在去重、过滤、移动零等问题里。

前缀和

如果题目反复问区间和，前缀和通常是第一反应。

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

前缀和的本质是把重复计算提前缓存起来。