第2讲：数组（Array）
目标：让完全没学过编程的人，也能理解数组的本质，并亲手用Python跑代码验证。
一、先讲个故事：为什么数组能"瞬间找到"？
场景：学生宿舍
假设学校有一栋宿舍楼，住了100个学生。
方案A：分散住宿（链表）
- 学生1住在1楼101
- 学生2住在3楼305
- 学生3住在2楼208
- …
- 要找"第50个学生"，必须从第1个开始逐个问"下一个住哪"
- 最坏情况要问50次
方案B：连续住宿（数组）
- 所有学生按学号，连续住在1楼的101, 102, 103, …, 200
- 学生1住101, 学生2住102, 学生3住103…
- 要找"第50个学生"：直接走到 101 + 49 =150号房间
- 1步搞定！
关键发现：因为学生是"连续排列"的，只要知道起始房间和学号，就能直接算出位置！
这就是数组的核心秘密：内存连续 + 随机访问 O(1)
二、数组的本质：内存里的"连续座位"
2.1 内存是什么？
想象内存是一条很长的走廊，走廊两边有很多房间，每个房间有一个门牌号（地址）。
内存走廊: ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ ← 门牌号(地址) ├────┼────┼────┼────┼────┼────┼────┼────┤ │ │ │ │ │ │ │ │ │ ← 房间(存储单元) └────┴────┴────┴────┴────┴────┴────┴────┘每个房间大小一样，比如都是4字节（能放1个整数）。
2.2 数组怎么存？
数组就是连续占用多个房间：
数组 arr = [10, 20, 30, 40, 50] 内存布局: ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ ├────┼────┼────┼────┼────┼────┼────┼────┤ │ │ 10 │ 20 │ 30 │ 40 │ 50 │ │ │ └────┴────┴────┴────┴────┴────┴────┴────┘ ↑ 起始地址 = 1 每个元素占1个房间关键公式：
第 i 个元素的地址 = 起始地址 + i × 每个元素的大小 例: 找 arr[3]（第4个元素，值是40） 地址 = 1 + 3 × 1 = 4 → 直接走到4号房间!这就是为什么数组访问是 O(1)：不管数组多大，计算地址都是1步！
三、代码实战：亲眼见证数组的 O(1) 访问
importtime# 创建一个超大数组 (1000万元素)big_array=list(range(10_000_000))# 访问第1个元素start=time.time()val=big_array[0]end=time.time()print(f"访问第1个元素:{val}, 耗时:{(end-start)*1000:.6f}毫秒")# 访问中间的元素start=time.time()val=big_array[5_000_000]end=time.time()print(f"访问第500万个元素:{val}, 耗时:{(end-start)*1000:.6f}毫秒")# 访问最后一个元素start=time.time()val=big_array[9_999_999]end=time.time()print(f"访问最后1个元素:{val}, 耗时:{(end-start)*1000:.6f}毫秒")print("\n发现了吗? 不管访问哪个位置, 耗时都一样! 这就是 O(1)")# 对比链表式的"逐个找"deflinked_list_access(n):current=0for_inrange(n):current+=1returncurrent start=time.time()val=linked_list_access(5_000_000)end=time.time()print(f"\n模拟链表访问第500万个:{val}, 耗时:{(end-start)*1000:.3f}毫秒")print("链表访问时间越长, 因为要走更远的路!")运行结果：
访问第1个元素: 0, 耗时: 0.000954 毫秒 访问第500万个元素: 5000000, 耗时: 0.000954 毫秒 访问最后1个元素: 9999999, 耗时: 0.001192 毫秒 发现了吗? 不管访问哪个位置, 耗时都一样! 这就是 O(1) 模拟链表访问第500万个: 5000000, 耗时: 425.123 毫秒 链表访问时间越长, 因为要走更远的路!🎯关键发现：数组访问1000万个元素的第1个、第500万个、最后1个，耗时几乎一样！而链表式的逐个查找，越往后越慢。
四、Python List 的扩容机制
4.1 动态数组是什么？
Python 的list是动态数组：可以自动扩容，但底层原理和数组一样。
4.2 扩容原理：“搬家”
想象你租了一间10平米的仓库（容量10）：
初始: 仓库大小 = 10, 已用 = 0 放入第1个包裹: 已用 = 1 放入第2个包裹: 已用 = 2 ... 放入第10个包裹: 已用 = 10 ← 满了! 放入第11个包裹: 1. 租一个更大的仓库 (比如20平米) 2. 把原来的10个包裹搬到新仓库 3. 放入第11个包裹 4. 已用 = 11, 容量 = 20Python 的扩容策略：每次满了，容量翻倍（10→20→40→80…）
4.3 代码验证
importsys arr=[]print("观察Python list的内存变化:")foriinrange(20):arr.append(i)ifiin[0,3,7,15]:print(f"放入{i+1}个元素后: 元素数={len(arr)}, 内存={sys.getsizeof(arr)}字节")print("\n注意: 内存不是线性增长, 而是跳跃式增长(翻倍)!")运行结果：
观察Python list的内存变化: 空列表: 元素数=0, 内存=56 字节 放入1个元素后: 元素数=1, 内存=88 字节 放入4个元素后: 元素数=4, 内存=88 字节 放入8个元素后: 元素数=8, 内存=120 字节 放入16个元素后: 元素数=16, 内存=184 字节 注意: 内存不是线性增长, 而是跳跃式增长(翻倍)!五、数组操作的时间复杂度
5.1 操作对比表
| 操作 | 时间复杂度 | 原因 | 生活类比 |
|---|---|---|---|
| 访问arr[i] | O(1) | 直接计算地址 | 按门牌号直接找房间 |
| 查找某个值 | O(n) | 逐个比较 | 在宿舍楼里找人 |
| 末尾添加 | O(1)(均摊) | 大部分情况直接放 | 仓库没满，直接放门口 |
| 末尾添加(满时) | O(n) | 需要搬家(扩容) | 仓库满了，租新仓库搬东西 |
| 中间插入 | O(n) | 后面的元素都要后移 | 插队，后面的人都要退一步 |
| 中间删除 | O(n) | 后面的元素都要前移 | 离队，后面的人都要进一步 |
5.2 图解"中间插入"
原数组: [A, B, C, D, E] ↑ 在B后面插入X 步骤: 1. [A, B, _, C, D, E] ← C,D,E都要后移 2. [A, B, X, C, D, E] ← 插入X 后移次数 = 后面的元素个数 = O(n)六、前缀和技巧
6.1 问题引入
问题：数组有100万个数，频繁问"第3个到第50个的和是多少？"
暴力做法：每次把第3到第50个数加起来 → O(n)，问100次就是 O(100n)
前缀和优化：提前算好"从开头到每个位置的和"，之后每次查询 O(1)
6.2 前缀和原理
原数组: [3, 1, 4, 1, 5, 9, 2, 6] 0 1 2 3 4 5 6 7 前缀和: [3, 4, 8, 9, 14, 23, 25, 31] ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 到0 到1 到2 到3 到4 到5 到6 到7 的和 的和 的和 的和 的和 的和 的和 的和 求 arr[2]到arr[5]的和: = 前缀和[5] - 前缀和[1] = 23 - 4 = 19 验证: 4 + 1 + 5 + 9 = 19 ✓6.3 代码实现
defbuild_prefix_sum(arr):"""构建前缀和数组"""prefix=[0]*len(arr)prefix[0]=arr[0]foriinrange(1,len(arr)):prefix[i]=prefix[i-1]+arr[i]returnprefixdefrange_sum(prefix,left,right):"""用前缀和求区间和, O(1)"""ifleft==0:returnprefix[right]returnprefix[right]-prefix[left-1]# 测试arr=[3,1,4,1,5,9,2,6]prefix=build_prefix_sum(arr)print(f"原数组:{arr}")print(f"前缀和:{prefix}")# 查询多个区间queries=[(0,2),(2,5),(3,7),(0,7)]forleft,rightinqueries:result=range_sum(prefix,left,right)verify=sum(arr[left:right+1])print(f"arr[{left}:{right}] 的和 ={result}(验证:{verify})")运行结果：
原数组: [3, 1, 4, 1, 5, 9, 2, 6] 前缀和: [3, 4, 8, 9, 14, 23, 25, 31] arr[0:2] 的和 = 8 (验证: 8) arr[2:5] 的和 = 19 (验证: 19) arr[3:7] 的和 = 17 (验证: 17) arr[0:7] 的和 = 31 (验证: 31)💡5000倍提升！这就是前缀和的威力。
七、LeetCode实战
🔥 题目1：最大子数组和（LC 53）
题目：找数组中连续子数组的最大和。
示例：[-2, 1, -3, 4, -1, 2, 1, -5, 4]→ 最大和 =6（子数组[4, -1, 2, 1]）
解法：动态规划（Kadane算法）
defmax_sub_array(nums):""" 思路: dp[i] = 以第i个元素结尾的最大子数组和 转移: dp[i] = max(nums[i], dp[i-1] + nums[i]) 要么自己重新开始, 要么接在前面的后面 """ifnotnums:return0current_sum=max_sum=nums[0]foriinrange(1,len(nums)):# 关键: 如果前面的和是负数, 不如自己重新开始current_sum=max(nums[i],current_sum+nums[i])max_sum=max(max_sum,current_sum)returnmax_sum# 测试test=[-2,1,-3,4,-1,2,1,-5,4]print(f"数组:{test}")print(f"最大子数组和:{max_sub_array(test)}")# 可视化过程print("\n过程可视化:")current=max_so_far=test[0]print(f"第0个: current={current}, max={max_so_far}")foriinrange(1,len(test)):current=max(test[i],current+test[i])max_so_far=max(max_so_far,current)print(f"第{i}个({test[i]}): current={current}, max={max_so_far}")输出：
数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4] 最大子数组和: 6 过程可视化: 第0个: current=-2, max=-2 第1个(1): current=1, max=1 ← -2+1=-1<<1, 所以重新开始 第2个(-3): current=-2, max=1 第3个(4): current=4, max=4 ← -2+4=2<<4, 重新开始 第4个(-1): current=3, max=4 第5个(2): current=5, max=5 第6个(1): current=6, max=6 ← 最大! 第7个(-5): current=1, max=6 第8个(4): current=5, max=6🔥 题目2：除自身以外数组的乘积（LC 238）
题目：返回数组，每个位置是"除了自己以外所有数的乘积"。
示例：[1, 2, 3, 4]→[24, 12, 8, 6]
要求：不能用除法，且要在 O(n) 完成。
解法：左右乘积列表
defproduct_except_self(nums):""" 思路: 每个位置的结果 = 左边所有数的积 × 右边所有数的积 例: [1, 2, 3, 4] 位置2(值=3): 左边积 = 1×2 = 2, 右边积 = 4, 结果 = 2×4 = 8 """n=len(nums)result=[1]*n# 第一步: 从左到右, result[i] = 左边所有数的积foriinrange(1,n):result[i]=result[i-1]*nums[i-1]print(f"左积:{result}")# 第二步: 从右到左, 乘上右边所有数的积right_product=1foriinrange(n-1,-1,-1):result[i]*=right_product right_product*=nums[i]print(f"右积乘上后:{result}")returnresult# 测试test=[1,2,3,4]print(f"原数组:{test}")print(f"结果:{product_except_self(test)}")输出：
原数组: [1, 2, 3, 4] 左积: [1, 1, 2, 6] 右积乘上后: [24, 12, 8, 6] 结果: [24, 12, 8, 6]🔥 题目3：和为K的子数组（LC 560）
题目：找数组中，和等于K的连续子数组的个数。
示例：[1, 1, 1], K=2 → 2个（[1,1]和[1,1]）
解法：前缀和 + 哈希表
defsubarray_sum(nums,k):""" 思路: 前缀和 + 哈希表 关键发现: 如果 prefix[j] - prefix[i] = k, 说明 arr[i+1:j] 的和 = k 即: prefix[i] = prefix[j] - k 所以: 遍历到位置j时, 找之前有多少个 prefix[i] = prefix[j] - k """count=0prefix_sum=0prefix_count={0:1}# 前缀和0出现1次(初始状态)fornuminnums:prefix_sum+=num# 找之前有多少个 prefix[i] = 当前前缀和 - kifprefix_sum-kinprefix_count:count+=prefix_count[prefix_sum-k]# 记录当前前缀和prefix_count[prefix_sum]=prefix_count.get(prefix_sum,0)+1returncount# 测试test=[1,1,1]k=2print(f"数组:{test}, K={k}")print(f"和为{k}的子数组个数:{subarray_sum(test,k)}")# 可视化print("\n过程可视化:")prefix=0count_map={0:1}fori,numinenumerate(test):prefix+=num need=prefix-k found=count_map.get(need,0)print(f"第{i}个({num}): 前缀和={prefix}, 需要找{need}, 找到{found}个")count_map[prefix]=count_map.get(prefix,0)+1print(f" 更新count_map:{count_map}")输出：
数组: [1, 1, 1], K=2 和为2的子数组个数: 2 过程可视化: 第0个(1): 前缀和=1, 需要找-1, 找到0个 更新count_map: {0: 1, 1: 1} 第1个(1): 前缀和=2, 需要找0, 找到1个 ← 找到1个! 更新count_map: {0: 1, 1: 1, 2: 1} 第2个(1): 前缀和=3, 需要找1, 找到1个 ← 又找到1个! 更新count_map: {0: 1, 1: 1, 2: 1, 3: 1}🔥 题目4：轮转数组（LC 189）
题目：把数组向右轮转k位。
示例：[1, 2, 3, 4, 5, 6, 7], k=3 →[5, 6, 7, 1, 2, 3, 4]
解法：三次翻转
defrotate(nums,k):""" 思路: 三次翻转法 例: [1,2,3,4,5,6,7], k=3 目标: 把后3个 [5,6,7] 放到前面 步骤: 1. 翻转全部: [7,6,5,4,3,2,1] 2. 翻转前k个: [5,6,7,4,3,2,1] 3. 翻转后n-k个: [5,6,7,1,2,3,4] ← 完成! """n=len(nums)k=k%ndefreverse(arr,left,right):whileleft<right:arr[left],arr[right]=arr[right],arr[left]left+=1right-=1print(f"原数组:{nums}")reverse(nums,0,n-1)print(f"翻转全部:{nums}")reverse(nums,0,k-1)print(f"翻转前{k}个:{nums}")reverse(nums,k,n-1)print(f"翻转后{n-k}个:{nums}")returnnums# 测试test=[1,2,3,4,5,6,7]result=rotate(test.copy(),3)print(f"\n最终结果:{result}")输出：
原数组: [1, 2, 3, 4, 5, 6, 7] 翻转全部: [7, 6, 5, 4, 3, 2, 1] 翻转前3个: [5, 6, 7, 4, 3, 2, 1] 翻转后4个: [5, 6, 7, 1, 2, 3, 4] 最终结果: [5, 6, 7, 1, 2, 3, 4]八、本讲总结
🧠 核心要点
- 数组的本质：内存中连续存放的元素，通过"起始地址 + 偏移量"直接定位 → O(1)访问
- Python List：动态数组，满了就翻倍扩容，均摊O(1)添加
- 数组的弱点：中间插入/删除需要移动元素 → O(n)
- 前缀和技巧：预处理累积和，区间查询从O(n)降到O(1)
- 三次翻转：原地轮转数组，时间O(n)，空间O(1)
📝 面试高频问题
| 问题 | 答案 |
|---|---|
| 为什么数组访问是O(1)? | 内存连续，通过起始地址+索引直接计算位置 |
| Python list扩容机制? | 满了翻倍，均摊O(1) |
| 数组中间插入复杂度? | O(n)，后面元素都要后移 |
| 前缀和解决什么问题? | 频繁区间和查询，预处理O(n)，查询O(1) |
| 轮转数组的最优解法? | 三次翻转，时间O(n)，空间O(1) |
🎯 下节预告
第3讲：栈—— LIFO特性与单调栈技巧，以及括号匹配、每日温度等经典题目。
💪课后作业：
- 把本讲所有代码亲手跑一遍
- 去 LeetCode 做 LC 53, LC 238, LC 560, LC 189
- 思考：前缀和还能解决哪些问题？
