数组基础与原地操作
复习索引和修改操作，了解数组面试中最常见的陷阱，例如下标偏移错误，以及迭代时修改列表。
数组基础与原地操作 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
数组作为连续内存
在底层，Python 列表由动态数组支持——这是一块连续的内存，其中的元素存储在连续的地址上。这种布局可以通过索引实现 O(1) 的随机访问：Python 能够立即计算出 address = base + index × element_size。在中间插入或删除元素需要移动后续的所有元素，成本为 O(n)。这种不对称性是数组面试中大多数权衡讨论的根源。
nums = [10, 20, 30, 40, 50]
# O(1) random access
print(nums[2]) # 30
print(nums[-1]) # 50
# O(1) append (amortised)
nums.append(60)
print(nums) # [10,20,30,40,50,60]
# O(n) insert at beginning
nums.insert(0, 0) # shifts all elements right
print(nums) # [0,10,20,30,40,50,60]差一错误：经典数组错误
差一错误是数组问题中最常见的错误答案来源。Python 使用从 0 开始的索引，因此最后一个有效索引是 len(arr) - 1。编写循环时，请使用最小有效输入（n=1 或 n=2）检查边界条件，以决定需要 < 还是 <=。提交前一定要用具体示例跟踪边界。
def find_max(nums):
# Use len(nums)-1 as last index
max_val = nums[0] # safe if n >= 1
for i in range(1, len(nums)): # start at 1, not 0
if nums[i] > max_val:
max_val = nums[i]
return max_val
print(find_max([3, 1, 4, 1, 5])) # 5
print(find_max([7])) # 7 (single element)
# Would crash if we accessed nums[len(nums)]使用双指针原地反转
原地反转数组时，可以使用从两端开始、向中间移动的两个指针，并不断交换它们指向的元素，直到两者相遇。这需要 O(1) 的额外空间和 O(n) 的时间。条件 left < right（严格小于）可以确保偶数长度和奇数长度都正确——元素个数为奇数时，中间元素会自动保持原位。
def reverse_inplace(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# Space: O(1) Time: O(n)
a = [1, 2, 3, 4, 5]
reverse_inplace(a)
print(a) # [5, 4, 3, 2, 1]
b = [1, 2, 3]
reverse_inplace(b)
print(b) # [3, 2, 1] middle element unchanged原地旋转数组
将数组向右旋转 k 个位置，可以通过反转三个部分来原地完成：先反转整个数组，再反转前 k 个元素，最后反转剩余的 n-k 个元素。这样可以达到 O(n) 的时间和 O(1) 的空间，远好于使用切片和拼接所需的 O(n) 空间。一定要先计算 k 对 n 的模，以处理 k ≥ n 的情况。
def rotate(nums, k):
n = len(nums)
k %= n # handle k >= n
def rev(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1; r -= 1
rev(0, n-1) # reverse all
rev(0, k-1) # reverse first k
rev(k, n-1) # reverse rest
a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
print(a) # [5, 6, 7, 1, 2, 3, 4]原地删除元素
原地删除重复值或目标值时，可以使用一个写指针跟踪下一个有效元素应写入的位置。读指针向前扫描；找到有效元素后，就将其复制到写入位置，并同时推进两个指针。这是 LeetCode 中“删除元素”“从有序数组中删除重复项”和“移动零”等问题的核心模式。
def remove_element(nums, val):
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
return write # new length
nums = [3, 2, 2, 3]
new_len = remove_element(nums, 3)
print(nums[:new_len]) # [2, 2]
nums2 = [0, 1, 2, 2, 3, 0, 4, 2]
new_len2 = remove_element(nums2, 2)
print(nums2[:new_len2]) # [0, 1, 3, 0, 4]移动零元素：读写指针
将所有零元素移到数组末尾，同时保持非零元素的顺序。读写指针方法会将每个非零元素放置到写入位置，然后用零元素填充末尾。另一种方法是将零元素向后交换，在无需第二次填充遍历的情况下保持顺序。两种方法的时间复杂度都是 O(n)，空间复杂度都是 O(1)。
def move_zeroes(nums):
write = 0
# Move all non-zeroes to front
for read in range(len(nums)):
if nums[read] != 0:
nums[write] = nums[read]
write += 1
# Fill rest with zeroes
while write < len(nums):
nums[write] = 0
write += 1
a = [0, 1, 0, 3, 12]
move_zeroes(a)
print(a) # [1, 3, 12, 0, 0]原地平方并排序
给定一个已排序的整数数组（可能包含负数），请返回一个按排序顺序排列的平方值数组。朴素方法是先平方再排序：O(n log n)。最优的双指针方法利用已排序输入中最大平方值来自两端这一事实：比较最左端和最右端元素的绝对值，并从右向左填充结果，时间复杂度为 O(n)。
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1 # fill from the right
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]查找枢轴并进行分区
荷兰国旗问题使用三个指针将数组原地划分为三个部分（小于、等于和大于枢轴）。这是快速排序的关键子步骤，也是 LeetCode 的“sort 颜色”问题的解法。维护这样的不变量：低位指针之前的元素都 < 枢轴，高位指针之后的元素都 > 枢轴，这推动了算法运行。
def sort_colors(nums):
# Dutch national flag: 0s, 1s, 2s
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # don't advance mid: new nums[mid] unexamined
a = [2, 0, 2, 1, 1, 0]
sort_colors(a)
print(a) # [0, 0, 1, 1, 2, 2]迭代时修改数组元素
迭代时可以安全地修改元素值（例如乘以 -1 来标记已访问元素），但在循环过程中绝不能改变列表长度。一种安全的编码技巧是：暂时将两个值编码到同一个整数中（例如使用符号位），从而在不分配额外空间的情况下，为每个元素模拟一个额外的布尔值。这种技巧会出现在“查找数组中所有缺失的数字”等问题中。
def find_disappeared(nums):
# Mark visited by negating the value at the index
for n in nums:
idx = abs(n) - 1
if nums[idx] > 0:
nums[idx] *= -1 # mark as seen
# Indices with positive values are missing
return [i + 1 for i, v in enumerate(nums) if v > 0]
print(find_disappeared([4, 3, 2, 7, 8, 2, 3, 1]))
# [5, 6] -- O(n) time, O(1) extra space数组面试模式检查清单
在编写任何数组问题的代码之前，请按以下思维清单逐项检查：
- 数组是否已排序？（可以使用双指针、二分查找）
- 元素是否有界（例如 1..n）？（可以使用基于索引的技巧）
- 是否要求原地操作？（使用读写指针或交换）
- 需要所有数对，还是只需要一个？（这会影响是否可以接受嵌套循环）
- 边界情况：空数组、单个元素、所有值都相同
def max_profit(prices):
# Pattern: single scan, track running minimum
# Time: O(n), Space: O(1)
if not prices: return 0 # edge case: empty
min_price = prices[0]
max_prof = 0
for price in prices[1:]: # start at index 1
max_prof = max(max_prof, price - min_price)
min_price = min(min_price, price)
return max_prof
print(max_profit([7, 1, 5, 3, 6, 4])) # 5
print(max_profit([7, 6, 4, 3, 1])) # 0卡丹算法：最大子数组
卡丹算法可以在 O(n) 时间和 O(1) 空间内找到和最大的连续子数组。每一步都要决定是扩展当前子数组，还是开始一个新子数组：current = max(num, current + num)。如果 current + num 小于单独的 num，说明当前子数组正在拉低总和，此时应重新开始。整个过程中要持续记录全局最大值。
def max_subarray(nums):
current = global_max = nums[0]
for n in nums[1:]:
current = max(n, current + n) # extend or restart
global_max = max(global_max, current)
return global_max
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# 6 (subarray [4, -1, 2, 1])
print(max_subarray([-1, -2, -3]))
# -1 (all negative: take the least negative)快速检查
测试您对本课“数据结构与算法——编程面试准备”相关概念的理解。
课程回顾
在本课中，您学习了：数组支持 O(1) 随机访问，但在中间插入和删除元素需要 O(n) 时间——了解这种不对称性有助于选择算法；读写指针模式可以在 O(n) 时间和 O(1) 空间内原地移除元素或移动值；以及符号位编码和将索引用作标记的技巧，可以为原本需要辅助数组的问题提供 O(1) 空间的解法。接下来，我们将学习前缀和与累计和。
常见问题解答
「数组基础与原地操作」课时是免费的吗？
是的 — 「数组基础与原地操作」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「数组基础与原地操作」这节课中我会学到什么？
复习索引和修改操作，了解数组面试中最常见的陷阱，例如下标偏移错误，以及迭代时修改列表。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「数组基础与原地操作」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 数组基础与原地操作
- 前缀和与累计总和
- 双指针：从两端向中间
- 双指针：快慢指针