数组基础与常用技巧

数组的内存模型

数组是最基础的数据结构。它的核心特征是：一块连续的内存空间，存储相同类型的元素。

这个"连续"不是随意的设计决策，而是一切特性的根源：

内存地址: 1000  1004  1008  1012  1016
           |     |     |     |     |
值:        [  3  |  7  |  1  |  9  |  5  ]
索引:        0     1     2     3     4

知道起始地址 base 和元素大小 size，第 i 个元素的地址 = base + i × size。这就是随机访问 O(1) 的原因——计算一个内存地址，一步到达。

与此相对，查询链表的第 i 个元素必须从头一步步跳转，O(n)。

操作复杂度

双指针技巧

双指针是解决数组问题最常用的技巧之一，分为两类：

对撞指针（两端向中间）

适用场景：有序数组，需要找满足某条件的一对元素。

经典题型：两数之和（有序版）、三数之和、接雨水、回文串判断。

// 两数之和（有序数组版）
// 时间 O(n)，空间 O(1)
int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;   // 和太小，左指针右移（增大）
        else right--;                    // 和太大，右指针左移（减小）
    }
    return new int[]{};
}

直觉：有序数组中，左端最小、右端最大。两指针从两端夹逼，每次根据结果决定移动哪端，每步都能排除一个元素，总共 O(n)。

快慢指针（同向，不同速度）

适用场景：去重、移除元素、找中间节点，在原数组上"覆盖"不需要的元素。

// 移除所有等于 val 的元素，返回新长度
// 时间 O(n)，空间 O(1)，原地操作
int removeElement(int[] nums, int val) {
    int slow = 0;  // slow 指向下一个"有效位置"
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];  // 把有效元素搬到 slow 位置
        }
        // fast 遇到 val 时跳过，slow 不动
    }
    return slow;  // slow 即为新数组长度
}

初始：[3, 2, 2, 3]，val = 3
fast=0: nums[0]=3=val，跳过
fast=1: nums[1]=2≠val，nums[0]=2，slow=1
fast=2: nums[2]=2≠val，nums[1]=2，slow=2
fast=3: nums[3]=3=val，跳过
结果：[2, 2, ?, ?]，返回 2

滑动窗口

滑动窗口是处理连续子数组问题的核心技巧，将暴力 O(n²) 降至 O(n)。

核心思想：维护一个"窗口"（left 到 right 的区间），窗口右边界向右扩张，当窗口不满足条件时，左边界收缩，始终保持窗口满足约束。

// 长度最小的子数组（子数组元素之和 >= target）
// 时间 O(n)，空间 O(1)
int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, minLen = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];           // 右边界扩张，加入新元素
        while (sum >= target) {       // 窗口满足条件时
            minLen = Math.min(minLen, right - left + 1);  // 更新答案
            sum -= nums[left++];      // 左边界收缩，尝试更短的窗口
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

滑动窗口的关键问题

1. 窗口内维护什么状态？（元素之和、字符频次……）
2. 何时扩右边界？（始终，每轮循环）
3. 何时收左边界？（窗口违反约束时）
4. 何时更新答案？（满足条件时，在收缩之前或收缩时）

前缀和

前缀和是处理区间查询的预处理技巧，把"计算子数组之和"从 O(n) 降至 O(1)（预处理 O(n)）。

// 构建前缀和数组
// prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
// prefix[0] = 0（哨兵，方便计算）
int[] buildPrefix(int[] nums) {
    int[] prefix = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
}

// 查询 [left, right] 区间的和：O(1)
int rangeSum(int[] prefix, int left, int right) {
    return prefix[right + 1] - prefix[left];
}

直觉：prefix[i] 表示从起点到 i 之前的总和，就像刻度尺上的累计距离。区间 [left, right] 的和 = 从起点到 right 的距离 - 从起点到 left 之前的距离，一减即得。

nums:    [2, 3, 1, 5, 4]
索引:      0  1  2  3  4
prefix:  [0, 2, 5, 6, 11, 15]
         ^
         哨兵 0

查询 [1, 3] 的和：prefix[4] - prefix[1] = 11 - 2 = 9
验证：3 + 1 + 5 = 9 ✓

差分数组

差分数组是前缀和的"逆操作"，专门处理频繁区间更新的场景。

场景：对数组进行 m 次"将区间 [l, r] 中所有元素加上 val"的操作，最后查询每个位置的最终值。

暴力做法：每次操作 O(n)，总计 O(mn)。 差分做法：每次操作 O(1)，最后 O(n) 还原，总计 O(m + n)。

// 差分数组核心操作
int[] diff = new int[n + 1];  // diff[i] = nums[i] - nums[i-1]

// 区间 [l, r] 加 val：仅修改两个端点
void add(int l, int r, int val) {
    diff[l] += val;       // l 处开始增加
    diff[r + 1] -= val;  // r+1 处结束增加
}

// 还原原数组：对差分数组做前缀和
int[] restore() {
    int[] nums = new int[n];
    nums[0] = diff[0];
    for (int i = 1; i < n; i++) {
        nums[i] = nums[i - 1] + diff[i];
    }
    return nums;
}

字符串处理技巧

字符串在 Java 中是不可变的 String 对象，频繁拼接时要用 StringBuilder（O(1) 摊销追加 vs String 拼接的 O(n)）。

字符频次统计

// 方法一：26 个小写字母时
int[] freq = new int[26];
for (char c : s.toCharArray()) {
    freq[c - 'a']++;
}

// 方法二：任意字符集时
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.merge(c, 1, Integer::sum);
}

双指针在字符串上的应用

回文串判断：对撞指针，从两端向中间比较。

boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left++) != s.charAt(right--)) return false;
    }
    return true;
}

边界问题与常见坑

(left + right) / 2 整数溢出

当 left 和 right 都很大时，两者相加可能溢出 int。

// 错误：可能溢出
int mid = (left + right) / 2;

// 正确：等价但不溢出
int mid = left + (right - left) / 2;

数组越界

访问 arr[i] 前，先确认 0 <= i < arr.length。尤其是 arr[i-1] 和 arr[i+1]，需要检查左右边界。

空数组与单元素

许多算法在空数组或单元素时有特殊行为，要在开头加判断：

if (nums == null || nums.length == 0) return 0;

小结

数组的核心优势是 O(1) 随机访问，来自连续内存的顺序编址。

四大技巧：