普通数组问题概述
数组是算法题中最基础也最灵活的数据结构。所谓"普通数组"，指不涉及树、图等复杂结构，纯粹在数组上进行操作，其解题技巧往往依赖于观察规律和巧妙的空间复用。
LeetCode 热门 100 题中，有五道经典题覆盖了数组操作的五个不同维度：
- 53. 最大子数组和 — 贪心 / DP 的简洁应用（Kadane 算法）。
- 56. 合并区间 — 排序后线性扫描，典型区间合并模板。
- 189. 轮转数组 — 原地翻转技巧，空间 O(1) 的反转三趟。
- 238. 除自身以外数组的乘积 — 前后缀积，避免除法。
- 41. 缺失的第一个正数 — 原地哈希，利用数组下标作桶。
它们各自代表了数组问题中一类常见的优化思路。下面逐一拆解。
1. 最大子数组和（LeetCode 53）
题目：给定整数数组 nums，找出一个具有最大和的连续子数组（至少包含一个元素），返回其最大和。
暴力法：枚举所有子数组，计算和，O(n²)。
优化思路（Kadane 算法）：
遍历数组，维护两个变量：currentSum 表示以当前元素结尾的子数组最大和，maxSum 记录全局最大和。递推公式为：
currentSum = max(nums[i], currentSum + nums[i])
maxSum = max(maxSum, currentSum)
即要么从当前元素重新开始，要么将当前元素追加到之前的子数组上。这本质是贪心或一维动态规划。
public int maxSubArray(int[] nums) {
int currentSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
复杂度：时间 O(n)，空间 O(1)。
关键点：当 currentSum 为负数时，舍弃之前的部分，从当前元素重新开始会更优。
2. 合并区间（LeetCode 56）
题目：给出一个区间的集合，合并所有重叠的区间。
优化思路（排序 + 线性扫描）： 先将区间按左端点升序排序。然后遍历区间，若当前区间的左端点 <= 上一个合并区间右端点，则合并（更新右端点为较大值）；否则，将上一个合并区间加入结果，开始新合并区间。
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) return intervals;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
int[] current = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= current[1]) {
current[1] = Math.max(current[1], intervals[i][1]);
} else {
merged.add(current);
current = intervals[i];
}
}
merged.add(current);
return merged.toArray(new int[merged.size()][]);
}
复杂度：排序 O(n log n)，扫描 O(n)，总时间 O(n log n)，空间 O(log n) 用于排序。
关键点：排序后只需要一次遍历；合并时右端点取两者最大值。
3. 轮转数组（LeetCode 189）
题目：将数组中的元素向右轮转 k 个位置。要求空间 O(1) 原地操作。
优化思路（三趟翻转）：
- 先对整个数组翻转。
- 再对前 k 个元素翻转（
k = k % n）。 - 最后对剩余元素翻转。
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int left, int right) {
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
复杂度：时间 O(n)，空间 O(1)。
关键点：k %= n 处理 k 大于数组长度的情况；翻转顺序不能颠倒。
4. 除自身以外数组的乘积（LeetCode 238）
题目：返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。要求不用除法，O(n) 时间。
优化思路（前后缀乘积）： 先用 answer 数组存储左侧乘积，然后从右往左乘以右侧乘积，滚动更新右侧乘积变量。
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
ans[0] = 1;
for (int i = 1; i < n; i++) {
ans[i] = ans[i-1] * nums[i-1];
}
int rightProduct = 1;
for (int i = n - 1; i >= 0; i--) {
ans[i] = ans[i] * rightProduct;
rightProduct *= nums[i];
}
return ans;
}
复杂度：时间 O(n)，空间 O(1)（除返回数组外）。
5. 缺失的第一个正数（LeetCode 41）
题目：找出未排序整数数组中没有出现的最小正整数。要求 O(n) 时间，O(1) 空间。
优化思路（原地哈希）：
将数组视为哈希表，下标 i 对应数值 i+1。遍历数组，将每个数放到它应该在的位置（即 nums[i] 应该在 nums[nums[i]-1] 处），交换直到当前位置的值是正确值或越界。然后再遍历一次，第一个 nums[i] != i+1 的位置就是缺失的最小正数。
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
复杂度：时间 O(n)（每个元素最多交换两次），空间 O(1)。
五题对比与启发
| 题目 | 核心技巧 | 时间复杂度 | 空间复杂度 | 关键特征 |
|---|---|---|---|---|
| 最大子数组和 | Kadane 贪心/DP | O(n) | O(1) | 递推当前最优，舍弃负数前缀 |
| 合并区间 | 排序 + 线性扫描 | O(n log n) | O(log n) | 按左端点排序，合并重叠 |
| 轮转数组 | 三次翻转 | O(n) | O(1) | 利用翻转交换前后块 |
| 除自身以外乘积 | 前后缀积 | O(n) | O(1) | 两次遍历，右侧乘积滚动 |
| 缺失第一个正数 | 原地哈希 | O(n) | O(1) | 利用下标做桶，交换归位 |
总结心法：
- 如果涉及子数组最值 → 考虑 Kadane 或 DP。
- 如果涉及区间合并 → 排序后线性扫描。
- 如果涉及循环移位 → 考虑翻转或取模映射。
- 如果涉及所有元素乘积（不含自身） → 用前后缀积空间优化。
- 如果涉及最小缺失正数 → 用原地哈希，通过交换把数放回"正确位置"。