本文档解释了 LeetCode 仓库中常用的数组问题模式和技术。数组是最基本的数据结构之一，构成了许多算法挑战的基础。我们专注于处理数组数据结构的有效方法，包括操作、搜索和优化。
有关特定数据结构的更多信息，请参阅 基本数据结构。有关相关的滑动窗口和双指针技术，请参阅 滑动窗口和双指针。
数组问题通常会归纳为几种常见的模式，这些模式在不同的问题中会反复出现。识别这些模式是高效解决数组相关挑战的关键。
来源: problems/26.remove-duplicates-from-sorted-array.md60-75), problems/283.move-zeroes.md35-45), problems/167.two-sum-ii-input-array-is-sorted.md38-45), problems/220.contains-duplicate-iii.md82-116)
双指针技术是解决数组问题最通用的方法之一。它涉及使用两个指针，它们可以
快慢指针以不同的速度遍历数组。此方法对于以下情况很有用：
在“删除排序数组中的重复项”中，我们使用慢指针来跟踪下一个唯一元素的位置
if (nums[fast] !== nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
来源: problems/26.remove-duplicates-from-sorted-array.md60-111), problems/142.Linked-List-Cycle-II.md66-110)
左右指针从数组的两端开始，向中间移动。这对于以下情况尤其有效：
对于已排序输入的“两数之和II”
left = 0, right = len(numbers) - 1
while left < right:
if numbers[left] + numbers[right] < target:
left += 1
if numbers[left] + numbers[right] > target:
right -= 1
if numbers[left] + numbers[right] == target:
return [left+1, right+1]
来源: problems/167.two-sum-ii-input-array-is-sorted.md147-157), problems/75.sort-colors.md54-97)
在这种变体中，一个指针遍历数组，而另一个指针将值写入正确的位置
对于“移动零”，读写方法可保持非零元素的顺序
let index = 0; // write pointer
for (let i = 0; i < nums.length; i++) { // read pointer
const num = nums[i];
if (num !== 0) {
nums[index++] = num;
}
}
来源: problems/283.move-zeroes.md35-72), problems/26.remove-duplicates-from-sorted-array.md99-111)
滑动窗口技术维护一个窗口（子数组），该窗口在数组中滑动，根据需要进行扩展或收缩。
对于需要处理固定大小子数组的问题
对于窗口大小根据条件变化的窗口
来源: problems/219.contains-duplicate-ii.md38-44), problems/220.contains-duplicate-iii.md102-116)
前缀和是一种技术，我们计算数组元素的累积和，从而能够进行 O(1) 的范围求和查询。
这项技术对于以下方面特别强大：
对于“两个不重叠子数组的最大和”问题
// Compute prefix sum
for (let i = 1; i < n + 1; i++) {
asum[i] = asum[i - 1] + a[i - 1]
}
来源: problems/1031.maximum-sum-of-two-non-overlapping-subarrays.md73-116), problems/152.maximum-product-subarray.md36-143)
哈希表和集合对于数组问题非常有用，尤其是当查找速度至关重要时。
用于跟踪特定距离内的元素
const visited = {};
for (let i = 0; i < nums.length; i++) {
if (visited[nums[i]] !== undefined && i - visited[nums[i]] <= k) {
return true;
}
visited[nums[i]] = i;
}
来源: problems/219.contains-duplicate-ii.md38-75), problems/349.intersection-of-two-arrays.md40-99)
对于“Contains Duplicate III”，桶方法根据值范围对元素进行分组
来源: problems/220.contains-duplicate-iii.md84-144)
这个巧妙的算法以 O(n) 的时间和 O(1) 的空间复杂度查找多数元素
多数元素的代码
let count = 1;
let majority = nums[0];
for (let i = 1; i < nums.length; i++) {
if (count === 0) {
majority = nums[i];
}
if (nums[i] === majority) {
count++;
} else {
count--;
}
}
用于查找多个多数元素
来源: problems/169.majority-element.md39-76), problems/229.majority-element-ii.md51-74)
一种三向分区方法，用于“排序颜色”等问题
实现模式
p0 = 0, p1 = 0, p2 = len(nums) - 1
while p1 <= p2:
if nums[p1] == 0: # Red
nums[p0], nums[p1] = nums[p1], nums[p0]
p0++
p1++
elif nums[p1] == 2: # Blue
nums[p1], nums[p2] = nums[p2], nums[p1]
p2--
else: # White
p1++
来源: problems/75.sort-colors.md40-151)
许多数组问题涉及动态规划方法，特别是子数组问题。
来源: problems/152.maximum-product-subarray.md36-142)
此表总结了常见数组操作的时间复杂度
| 操作 | 未排序数组 | 已排序数组 | 基于哈希 |
|---|---|---|---|
| 搜索 | O(n) | O(log n) | O(1) |
| 插入 | O(1) (尾部) | O(n) | O(1) |
| 删除 | O(n) | O(n) | O(1) |
| 查找最小值/最大值 | O(n) | O(1) | O(n) |
| 查找重复项 | O(n²) 或 O(n log n) | O(n) | O(n) |
| 两数之和 | O(n²) 或 O(n log n) | O(n) | O(n) |
来源：problems/167.two-sum-ii-input-array-is-sorted.md38-45), problems/26.remove-duplicates-from-sorted-array.md170-173), problems/219.contains-duplicate-ii.md131-134)
许多数组问题要求原地修改，以达到 O(1) 的空间复杂度
原地删除重复项
let slowP = 0;
for (let fastP = 0; fastP < size; fastP++) {
if (nums[fastP] !== nums[slowP]) {
slowP++;
nums[slowP] = nums[fastP];
}
}
return slowP + 1;
来源：problems/26.remove-duplicates-from-sorted-array.md98-111), problems/283.move-zeroes.md98-136)
在解决数组问题时，请注意这些常见的边缘情况
来源：problems/152.maximum-product-subarray.md129-136), problems/26.remove-duplicates-from-sorted-array.md87-88), problems/169.majority-element.md58-61)
此表总结了存储库中的关键数组问题类型
| 问题类型 | 示例 | 关键技术 |
|---|---|---|
| 删除重复项 | 26. 删除排序数组中的重复项 | 双指针（快慢指针） |
| 移动元素 | 283. 移动零 | 双指针（读写指针） |
| 查找元素 | 167. 两数之和 II - 输入数组已排序 | 双指针（左右指针） |
| 众数 | 169. 多数元素 | Boyer-Moore 投票算法 |
| 排序 | 75. 颜色分类 | 荷兰国旗问题 |
| 最大子数组 | 152. 乘积最大子数组 | 动态规划 |
| 存在重复元素 | 219. 存在重复元素 II | 哈希表 |
| 不重叠子数组 | 1031. 两个非重叠子数组的最大和 | 前缀和 + 动态规划 |
来源：problems/26.remove-duplicates-from-sorted-array.md), problems/283.move-zeroes.md), problems/167.two-sum-ii-input-array-is-sorted.md), problems/169.majority-element.md), problems/75.sort-colors.md), problems/152.maximum-product-subarray.md), problems/219.contains-duplicate-ii.md), problems/1031.maximum-sum-of-two-non-overlapping-subarrays.md)