第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_arraylist(range(10_000_000))# 访问第1个元素starttime.time()valbig_array[0]endtime.time()print(f访问第1个元素:{val}, 耗时:{(end-start)*1000:.6f}毫秒)# 访问中间的元素starttime.time()valbig_array[5_000_000]endtime.time()print(f访问第500万个元素:{val}, 耗时:{(end-start)*1000:.6f}毫秒)# 访问最后一个元素starttime.time()valbig_array[9_999_999]endtime.time()print(f访问最后1个元素:{val}, 耗时:{(end-start)*1000:.6f}毫秒)print(\n发现了吗? 不管访问哪个位置, 耗时都一样! 这就是 O(1))# 对比链表式的逐个找deflinked_list_access(n):current0for_inrange(n):current1returncurrent starttime.time()vallinked_list_access(5_000_000)endtime.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放入{i1}个元素后: 元素数{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)ifleft0:returnprefix[right]returnprefix[right]-prefix[left-1]# 测试arr[3,1,4,1,5,9,2,6]prefixbuild_prefix_sum(arr)print(f原数组:{arr})print(f前缀和:{prefix})# 查询多个区间queries[(0,2),(2,5),(3,7),(0,7)]forleft,rightinqueries:resultrange_sum(prefix,left,right)verifysum(arr[left:right1])print(farr[{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_summax_sumnums[0]foriinrange(1,len(nums)):# 关键: 如果前面的和是负数, 不如自己重新开始current_summax(nums[i],current_sumnums[i])max_summax(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过程可视化:)currentmax_so_fartest[0]print(f第0个: current{current}, max{max_so_far})foriinrange(1,len(test)):currentmax(test[i],currenttest[i])max_so_farmax(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): current1, max1 ← -21-11, 所以重新开始 第2个(-3): current-2, max1 第3个(4): current4, max4 ← -2424, 重新开始 第4个(-1): current3, max4 第5个(2): current5, max5 第6个(1): current6, max6 ← 最大! 第7个(-5): current1, max6 第8个(4): current5, max6 题目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 nlen(nums)result[1]*n# 第一步: 从左到右, result[i] 左边所有数的积foriinrange(1,n):result[i]result[i-1]*nums[i-1]print(f左积:{result})# 第二步: 从右到左, 乘上右边所有数的积right_product1foriinrange(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], K2 → 2个[1,1]和[1,1]解法前缀和 哈希表defsubarray_sum(nums,k): 思路: 前缀和 哈希表 关键发现: 如果 prefix[j] - prefix[i] k, 说明 arr[i1:j] 的和 k 即: prefix[i] prefix[j] - k 所以: 遍历到位置j时, 找之前有多少个 prefix[i] prefix[j] - k count0prefix_sum0prefix_count{0:1}# 前缀和0出现1次(初始状态)fornuminnums:prefix_sumnum# 找之前有多少个 prefix[i] 当前前缀和 - kifprefix_sum-kinprefix_count:countprefix_count[prefix_sum-k]# 记录当前前缀和prefix_count[prefix_sum]prefix_count.get(prefix_sum,0)1returncount# 测试test[1,1,1]k2print(f数组:{test}, K{k})print(f和为{k}的子数组个数:{subarray_sum(test,k)})# 可视化print(\n过程可视化:)prefix0count_map{0:1}fori,numinenumerate(test):prefixnum needprefix-k foundcount_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], K2 和为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], k3 →[5, 6, 7, 1, 2, 3, 4]解法三次翻转defrotate(nums,k): 思路: 三次翻转法 例: [1,2,3,4,5,6,7], k3 目标: 把后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] ← 完成! nlen(nums)kk%ndefreverse(arr,left,right):whileleftright:arr[left],arr[right]arr[right],arr[left]left1right-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]resultrotate(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思考前缀和还能解决哪些问题
第2讲：数组（Array）
第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_arraylist(range(10_000_000))# 访问第1个元素starttime.time()valbig_array[0]endtime.time()print(f访问第1个元素:{val}, 耗时:{(end-start)*1000:.6f}毫秒)# 访问中间的元素starttime.time()valbig_array[5_000_000]endtime.time()print(f访问第500万个元素:{val}, 耗时:{(end-start)*1000:.6f}毫秒)# 访问最后一个元素starttime.time()valbig_array[9_999_999]endtime.time()print(f访问最后1个元素:{val}, 耗时:{(end-start)*1000:.6f}毫秒)print(\n发现了吗? 不管访问哪个位置, 耗时都一样! 这就是 O(1))# 对比链表式的逐个找deflinked_list_access(n):current0for_inrange(n):current1returncurrent starttime.time()vallinked_list_access(5_000_000)endtime.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放入{i1}个元素后: 元素数{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)ifleft0:returnprefix[right]returnprefix[right]-prefix[left-1]# 测试arr[3,1,4,1,5,9,2,6]prefixbuild_prefix_sum(arr)print(f原数组:{arr})print(f前缀和:{prefix})# 查询多个区间queries[(0,2),(2,5),(3,7),(0,7)]forleft,rightinqueries:resultrange_sum(prefix,left,right)verifysum(arr[left:right1])print(farr[{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_summax_sumnums[0]foriinrange(1,len(nums)):# 关键: 如果前面的和是负数, 不如自己重新开始current_summax(nums[i],current_sumnums[i])max_summax(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过程可视化:)currentmax_so_fartest[0]print(f第0个: current{current}, max{max_so_far})foriinrange(1,len(test)):currentmax(test[i],currenttest[i])max_so_farmax(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): current1, max1 ← -21-11, 所以重新开始 第2个(-3): current-2, max1 第3个(4): current4, max4 ← -2424, 重新开始 第4个(-1): current3, max4 第5个(2): current5, max5 第6个(1): current6, max6 ← 最大! 第7个(-5): current1, max6 第8个(4): current5, max6 题目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 nlen(nums)result[1]*n# 第一步: 从左到右, result[i] 左边所有数的积foriinrange(1,n):result[i]result[i-1]*nums[i-1]print(f左积:{result})# 第二步: 从右到左, 乘上右边所有数的积right_product1foriinrange(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], K2 → 2个[1,1]和[1,1]解法前缀和 哈希表defsubarray_sum(nums,k): 思路: 前缀和 哈希表 关键发现: 如果 prefix[j] - prefix[i] k, 说明 arr[i1:j] 的和 k 即: prefix[i] prefix[j] - k 所以: 遍历到位置j时, 找之前有多少个 prefix[i] prefix[j] - k count0prefix_sum0prefix_count{0:1}# 前缀和0出现1次(初始状态)fornuminnums:prefix_sumnum# 找之前有多少个 prefix[i] 当前前缀和 - kifprefix_sum-kinprefix_count:countprefix_count[prefix_sum-k]# 记录当前前缀和prefix_count[prefix_sum]prefix_count.get(prefix_sum,0)1returncount# 测试test[1,1,1]k2print(f数组:{test}, K{k})print(f和为{k}的子数组个数:{subarray_sum(test,k)})# 可视化print(\n过程可视化:)prefix0count_map{0:1}fori,numinenumerate(test):prefixnum needprefix-k foundcount_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], K2 和为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], k3 →[5, 6, 7, 1, 2, 3, 4]解法三次翻转defrotate(nums,k): 思路: 三次翻转法 例: [1,2,3,4,5,6,7], k3 目标: 把后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] ← 完成! nlen(nums)kk%ndefreverse(arr,left,right):whileleftright:arr[left],arr[right]arr[right],arr[left]left1right-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]resultrotate(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思考前缀和还能解决哪些问题
