做这行这么多年看过的教程和源码笔记不少但每次回头翻数组相关的笔记还是觉得这东西最容易被低估。很多人觉得数组简单无非是连续内存、下标访问真正写起代码来却屡屡在扩容策略、边界条件、多维遍历上栽跟头。我手里这份《数组相关笔记1.7-1.9》刚好整理的就是从底层模型到实际应用这段最关键的内容覆盖了数组的内存布局、操作复杂度、经典应用场景和常见坑点。无论你是刚接触数据结构的初学者还是准备面试想快速过一遍核心知识的开发者这份笔记都能帮你把数组从好像会了变成真的稳了。1. 数组的本质连续内存背后的设计逻辑1.1 为什么下标从0开始这是每一个学数组的人都会碰到的问题也是1.7节里最先展开的内容。数组在内存中是一段连续的存储空间每个元素占据固定大小的字节数比如int占4字节、double占8字节。访问某个下标i对应的元素时CPU实际做的事情是一次加法运算起始地址 i * 元素大小。如果下标从1开始公式就变成起始地址 (i - 1) * 元素大小每次访问都要多做一次i - 1的减法。别小看这个减法在循环密集的场景下这意味着一整条指令流水线都会被拖慢。从编译器和CPU的角度来说下标从0开始是一种让硬件少干活的设计。我从实际写代码的感受来说从0开始还有一个附带好处区间表示更加自然。比如一个长度为n的数组合法下标是0到n-1如果用左闭右开区间[0, n)来描述遍历范围代码写起来不容易出现差一错误。当然也有一些语言比如早期的BASIC选择下标从1开始纯粹是为了人类直觉。但从系统底层效率和工程惯性的角度0起始已经成了绝对主流。我的建议是别去纠结哪种更好而是把起始地址 偏移量这个模型刻在脑子里以后学指针、学切片、学缓存友好性都会顺很多。1.2 静态数组与动态数组绕不开的扩容话题笔记1.7里同时提到了静态数组和动态数组的对比。所谓静态数组就是声明时就确定长度比如C语言里的int arr[10]编译期分配在栈上长度不可变。动态数组则是运行时可以增长的结构比如C里的vector、Java里的ArrayList、Python里的list。动态数组的核心机制是扩容。以Python列表为例当append时发现容量不够解释器会申请一块更大的内存通常是原来容量的1.125倍也就是多8分之一的增量然后把旧元素逐个拷贝过去最后释放旧内存。这个过程叫realloc在C层面就是realloc函数干的事。很多初学者不理解为什么扩容不是用多少扩多少而是一次扩充一大块。原因在于如果每次增加一个元素就申请一次内存append操作的时间复杂度会退化成O(n)因为每次都要做内存拷贝。而按比例预扩容虽然单次扩容很慢但均摊下来每次append接近O(1)。这个均摊复杂度概念我在笔记里专门圈了出来它不仅能解释Python列表的行为还能帮你理解哈希表、流式处理等很多场景下的性能表现。实操建议在已知元素规模时尽量预先分配足够容量。比如Python里用[0] * n先占位Java里new ArrayList(initialCapacity)明确初始大小能明显减少扩容次数。我实测过向一个100万元素的列表逐个append预先分配容量大约能省掉30%左右的耗时主要就省在减少内存拷贝和realloc调用上。2. 数组的核心操作与时间复杂度把增删改查彻底吃透2.1 访问、查找、插入、删除谁快谁慢一目了然笔记1.8的重点是数组操作的复杂度分析。先给出结论表格操作时间复杂度说明按下标访问O(1)直接算地址最快遍历全部元素O(n)必须逐个访问按值查找无序O(n)线性扫描按值查找有序O(log n)二分查找尾部插入/删除O(1) 均摊动态数组扩容后可尾插任意位置插入/删除O(n)需要搬移元素这里面最值得深挖的是任意位置插入和删除的O(n)。比如在长度为n的数组第k个位置插入一个新元素需要把从k到n-1的所有元素都往后挪一格循环次数是n-k。最坏情况下往头部插入要搬移n个元素平均情况下插入位置均匀分布期望搬移次数是n/2所以平均时间复杂度就是O(n)。删除同理要把后半段整体往前挪。我见过不少同学在实际编码时忽略了这一点。比如写了一个循环在数组头部反复插入数据结果数据量一大就直接超时。这里的教训是如果频繁在头部操作优先考虑用链表链表头插O(1)或者干脆把数组反转过来把头部操作变成尾部操作。2.2 动态扩容的均摊分析Python列表的append为什么是O(1)1.8节里有一个推导过程澄清很多人对动态数组扩容的误解。假设数组初始容量是1扩容策略是容量翻倍那么从容量1增长到容量n总共需要做多少次元素拷贝答案是1 2 4 ... n/2 n这是一个等比数列总和约等于2n。也就是说经历n次插入总的拷贝成本是2n均摊到每一次插入就是常数级别O(1)。这就是倍增扩容的数学依据。反过来如果扩容策略是每次只增加1个容量那么前n次插入的总拷贝量是1 2 3 ... n约等于n^2/2均摊下来就是O(n)这是完全不可接受的。知道这个原理后有几个实际问题会有更清晰的理解Python列表为什么建议用append而不是insert(0, x)前面说过头插是O(n)还有一个原因是头插会引起整个数组的搬移哪怕容量够用也一样。为什么某些库的列表缩容时不是立刻缩比如Cvector的shrink_to_fit是显式调用才触发因为频繁缩容会造成抖动反复申请释放内存性能反而更糟。扩容倍数为什么通常是1.5倍或2倍太小则扩容频繁太大则浪费内存。1.5倍在某种内存分配策略下更容易复用旧内存块2倍则实现最简单。这是工程上的权衡没有绝对正确。我在笔记里顺手画了一张内存搬运示意图旧数组被标记为待释放新数组接收原元素拷贝后续新增元素写入新数组的空闲区。理解这张图你就理解了动态数组的全部精髓。3. 数组的经典应用场景与算法思想3.1 双指针技巧有序数组的精简艺术1.9节一上来就是双指针。数组天然适合双指针因为它支持O(1)的随机访问两个指针可以在一次遍历内完成很多看似需要嵌套循环的任务。我最常用的三个场景两数之和有序数组版本。给定一个升序排列的数组和一个目标值找到两个数使它们的和等于目标值。暴力做法是O(n^2)双重循环双指针的做法是左指针指向开头右指针指向末尾计算当前和。如果和大于目标值右指针左移如果和小于目标值左指针右移如果相等就找到了答案。两个指针最多走完整数组一遍时间复杂度O(n)。移除重复元素。要求原地修改数组让每个元素只出现一次。做法是快慢指针快指针负责探索整个数组慢指针负责维护去重后数组的末尾位置。每当快指针遇到一个与慢指针指向位置不同的元素就把它复制到慢指针的下一个位置同时慢指针前进。最终慢指针的位置就是新数组的长度。容器盛水问题。这是双指针里偏难的一道题核心在于每次移动高度较矮的那一侧指针因为面积受矮的一侧制约。这个问题的证明要看懂移动较矮侧不会错过最优解这一点我在笔记里用了具体的实例展开推导花了不少篇幅。双指针之所以好用源于一个简单事实数组是有序的或可以排序指针移动方向是单调的不会回退所以不会重复计算也不会遗漏。这个单调性是理解双指针解题正确性的关键。3.2 前缀和与差分数组区间问题的杀手锏如果说双指针是面向前向遍历的优化前缀和就是面向区间查询的优化。定义很简单pre[i]表示数组前i个元素的和。有了pre数组查询区间[l, r]的和只需要pre[r1] - pre[l]一次减法搞定时间复杂度O(1)。如果没有前缀和每次查询都要重头遍历区间假设有m次查询、数组长度n总时间复杂度是O(m*n)。一旦n和m都到10^5级别运算量就到10^10了程序基本卡死。用前缀和后预处理O(n) 查询O(1)整体O(nm)这是数量级的提升。我举个例子。你有一个每日销售额数组要频繁回答从第3天到第7天总共卖了多少。直接算当然可以但如果是2000个这样的问题就得循环2000次。前缀和的做法是先把pre[i] pre[i-1] arr[i]准备好每个问题变成pre[7] - pre[2]快得离谱。差分数组则跟前缀和刚好是逆运算。它的应用场景是区间修改给某个区间的所有元素同时加一个值最后再求整个数组被改成了什么样。朴素做法是每次遍历区间加值m次操作就是O(m*n)。差分数组的做法是维护一个diff数组区间[l, r]加val时只做diff[l] valdiff[r1] - val所有区间更新完后再做一次前缀和恢复出目标数组。整个流程O(mn)。这两个数据结构放在一起学特别有意思它们反映了一种空间换时间的思维用O(n)的额外存储把高频重复计算变成常量时间的查表。这种思维方式不仅写算法题有用日常处理日志聚合、时间段统计、报表生成时也经常用到。3.3 数组是哈希表的亲爹哈希冲突处理剖析很多人没有意识到哈希表HashMap、dict的底层就是数组。哈希表的存储主体是一个数组每个数组元素称为桶bucket键通过哈希函数映射到某个桶的下标值就存在那个桶里。哈希冲突是必然要处理的问题。主流方案有两种链地址法和开放寻址法。链地址法就是数组每个桶挂一条链表冲突的元素挂在同一条链上Java里当链表过长时还会转成红黑树就是为了把最坏情况从O(n)降到O(log n)。开放寻址法则是在冲突时向后探查空位Python的dict用的就是改良后的开放寻址法。这跟数组笔记有什么关系关系太大了。正因为数组支持O(1)的随机访问哈希表才能做到O(1)的平均查找时间。当你理解了哈希函数算出下标 → 数组访问对应桶 → 处理冲突这条链路你就不会再疑惑为什么自定义对象的hashCode和equals要一起重写也不会在分析哈希表性能时一头雾水。我在笔记里建议所有学数组的人把哈希表的实现思路自己写一遍哪怕是伪代码也好。很多知识只有当你意识到数组下标其实是个可以直接寻址的索引时才会真正打通。4. 数组实操中的常见问题与排查技巧4.1 值得反复强调的是边界数组越界的隐蔽性数组越界是最常见也最麻烦的运行时错误。在C/C里越界不会报错而是直接访问了相邻内存这在工程上可能造成数据篡改、程序崩溃甚至安全漏洞。Python和Java会抛出异常但这类异常一旦在生产环境出现通常意味着前面的逻辑已经有了漏洞。我总结了几条防越界的实操经验循环变量初始值设为0循环条件写成i n不要写成i n。凡是涉及i1、i-1的下标操作先确认当前i的范围边界。二维数组遍历时优先用外层行、内层列的顺序并且逐层检查行列越界。用切片操作时明确切片的区间语义比如Python的arr[a:b]是左闭右开包含a不包含b写错了会silently返回空结果而不是报错。记忆技巧是数组下标的合法范围永远从0开始到长度减1为止。把这个结论刻在肌肉记忆里很多问题能避免一大半。4.2 拷贝陷阱浅拷贝与深拷贝数组拷贝也是个重灾区。很多人以为arr2 arr1就是拷贝实际上这只是把arr2指向了同一个数组对象修改任何一个都会影响另一个。真正的拷贝方式取决于语言和需求C语言用memcpy逐字节拷贝或者写循环逐个赋值。JavaArrays.copyOf和System.arraycopy是浅拷贝元素是引用时只拷贝引用clone()同理要深拷贝得自己遍历并逐个new对象。Pythonnew_list old_list[:]是浅拷贝copy.deepcopy(old_list)才是深拷贝。Cstd::vector的拷贝构造函数是深拷贝但元素本身是否深拷贝取决于元素类型。在写回溯算法、动态规划状态复制时浅拷贝和深拷贝的区别尤其要命。我踩过一次坑状态数组只做了浅拷贝结果修改新数组时把原数组也改了回溯逻辑直接全乱。从那之后我每次复制数组都会先问自己一句里面的元素是基本类型还是对象如果是对象我需要共享引用还是独立副本4.3 面试/笔试中的数组高频题型清单笔记最后整理了一份练习题清单我这里按难度分类列一下方便自查难度题型核心考察点基础移除元素、去重排序双指针、原地操作基础最大子数组和动态规划、前缀和变体中等旋转数组、矩阵转置下标映射、规律发现中等合并两个有序数组从后向前双指针中等前缀和区间查询前缀和预处理进阶盛最多水的容器双指针、移动矮侧推导进阶差分数组区间更新差分、批量修改这些题目绕不开两个共同能力一是把问题抽象成下标之间的关系二是控制好遍历过程中的边界。说白了数组题考的就是你能否在连续内存的思维框架里熟练地操控下标、边界和区间。从我个人的刷题和工程实践来看数组刷题不要贪多吃透每一种题型背后的一两个标准解法就够了。比如双指针你只要真正理解移动条件为什么成立就能迁移到十几道题上前缀和只要理解预处理换查询速度的思想很多区间问题都能一套思路带过。5. 我的学习建议数组笔记怎么用最见效这套笔记1.7到1.9本身是按照底层基础 → 操作复杂度 → 应用场景 → 踩坑总结的顺序组织的我建议你也按这个顺序消化不要跳着看。底层模型是地基不搞懂下标和内存的关系后面所有边界判断都是空中楼阁。操作复杂度决定了你要不要优化、有没有优化的必要学完这个你才会明白为什么有时候看起来很笨的方法反而是最优解。看的时候动手写代码。每个操作比如插入、删除、扩容、切片都自己实现一遍哪怕是造轮子也没关系。我自己的经验是只看不动手过一周再回头就连双指针的移动条件都记不清了。写一遍跑通再故意写错几个边界条件观察报错和输出差异这个印象能保持很久。最后一个小技巧给数组相关题目准备一个环境清单也就是把语言里数组切片的语法、越界行为的差异、动态扩容的触发条件列在一起。遇到具体语言写代码前先扫一眼清单能节省不少查文档的时间。数组是整个数据结构大厦的第一块砖也是最需要被理解透的一块砖。把这些内容吃透后面学链表、栈、队列、哈希表都能举一反三。毕竟很多高级数据结构的底层最后还是一段连续的内存——一个老老实实的数组。
做这行这么多年看过的教程和源码笔记不少但每次回头翻数组相关的笔记还是觉得这东西最容易被低估。很多人觉得数组简单无非是连续内存、下标访问真正写起代码来却屡屡在扩容策略、边界条件、多维遍历上栽跟头。我手里这份《数组相关笔记1.7-1.9》刚好整理的就是从底层模型到实际应用这段最关键的内容覆盖了数组的内存布局、操作复杂度、经典应用场景和常见坑点。无论你是刚接触数据结构的初学者还是准备面试想快速过一遍核心知识的开发者这份笔记都能帮你把数组从好像会了变成真的稳了。1. 数组的本质连续内存背后的设计逻辑1.1 为什么下标从0开始这是每一个学数组的人都会碰到的问题也是1.7节里最先展开的内容。数组在内存中是一段连续的存储空间每个元素占据固定大小的字节数比如int占4字节、double占8字节。访问某个下标i对应的元素时CPU实际做的事情是一次加法运算起始地址 i * 元素大小。如果下标从1开始公式就变成起始地址 (i - 1) * 元素大小每次访问都要多做一次i - 1的减法。别小看这个减法在循环密集的场景下这意味着一整条指令流水线都会被拖慢。从编译器和CPU的角度来说下标从0开始是一种让硬件少干活的设计。我从实际写代码的感受来说从0开始还有一个附带好处区间表示更加自然。比如一个长度为n的数组合法下标是0到n-1如果用左闭右开区间[0, n)来描述遍历范围代码写起来不容易出现差一错误。当然也有一些语言比如早期的BASIC选择下标从1开始纯粹是为了人类直觉。但从系统底层效率和工程惯性的角度0起始已经成了绝对主流。我的建议是别去纠结哪种更好而是把起始地址 偏移量这个模型刻在脑子里以后学指针、学切片、学缓存友好性都会顺很多。1.2 静态数组与动态数组绕不开的扩容话题笔记1.7里同时提到了静态数组和动态数组的对比。所谓静态数组就是声明时就确定长度比如C语言里的int arr[10]编译期分配在栈上长度不可变。动态数组则是运行时可以增长的结构比如C里的vector、Java里的ArrayList、Python里的list。动态数组的核心机制是扩容。以Python列表为例当append时发现容量不够解释器会申请一块更大的内存通常是原来容量的1.125倍也就是多8分之一的增量然后把旧元素逐个拷贝过去最后释放旧内存。这个过程叫realloc在C层面就是realloc函数干的事。很多初学者不理解为什么扩容不是用多少扩多少而是一次扩充一大块。原因在于如果每次增加一个元素就申请一次内存append操作的时间复杂度会退化成O(n)因为每次都要做内存拷贝。而按比例预扩容虽然单次扩容很慢但均摊下来每次append接近O(1)。这个均摊复杂度概念我在笔记里专门圈了出来它不仅能解释Python列表的行为还能帮你理解哈希表、流式处理等很多场景下的性能表现。实操建议在已知元素规模时尽量预先分配足够容量。比如Python里用[0] * n先占位Java里new ArrayList(initialCapacity)明确初始大小能明显减少扩容次数。我实测过向一个100万元素的列表逐个append预先分配容量大约能省掉30%左右的耗时主要就省在减少内存拷贝和realloc调用上。2. 数组的核心操作与时间复杂度把增删改查彻底吃透2.1 访问、查找、插入、删除谁快谁慢一目了然笔记1.8的重点是数组操作的复杂度分析。先给出结论表格操作时间复杂度说明按下标访问O(1)直接算地址最快遍历全部元素O(n)必须逐个访问按值查找无序O(n)线性扫描按值查找有序O(log n)二分查找尾部插入/删除O(1) 均摊动态数组扩容后可尾插任意位置插入/删除O(n)需要搬移元素这里面最值得深挖的是任意位置插入和删除的O(n)。比如在长度为n的数组第k个位置插入一个新元素需要把从k到n-1的所有元素都往后挪一格循环次数是n-k。最坏情况下往头部插入要搬移n个元素平均情况下插入位置均匀分布期望搬移次数是n/2所以平均时间复杂度就是O(n)。删除同理要把后半段整体往前挪。我见过不少同学在实际编码时忽略了这一点。比如写了一个循环在数组头部反复插入数据结果数据量一大就直接超时。这里的教训是如果频繁在头部操作优先考虑用链表链表头插O(1)或者干脆把数组反转过来把头部操作变成尾部操作。2.2 动态扩容的均摊分析Python列表的append为什么是O(1)1.8节里有一个推导过程澄清很多人对动态数组扩容的误解。假设数组初始容量是1扩容策略是容量翻倍那么从容量1增长到容量n总共需要做多少次元素拷贝答案是1 2 4 ... n/2 n这是一个等比数列总和约等于2n。也就是说经历n次插入总的拷贝成本是2n均摊到每一次插入就是常数级别O(1)。这就是倍增扩容的数学依据。反过来如果扩容策略是每次只增加1个容量那么前n次插入的总拷贝量是1 2 3 ... n约等于n^2/2均摊下来就是O(n)这是完全不可接受的。知道这个原理后有几个实际问题会有更清晰的理解Python列表为什么建议用append而不是insert(0, x)前面说过头插是O(n)还有一个原因是头插会引起整个数组的搬移哪怕容量够用也一样。为什么某些库的列表缩容时不是立刻缩比如Cvector的shrink_to_fit是显式调用才触发因为频繁缩容会造成抖动反复申请释放内存性能反而更糟。扩容倍数为什么通常是1.5倍或2倍太小则扩容频繁太大则浪费内存。1.5倍在某种内存分配策略下更容易复用旧内存块2倍则实现最简单。这是工程上的权衡没有绝对正确。我在笔记里顺手画了一张内存搬运示意图旧数组被标记为待释放新数组接收原元素拷贝后续新增元素写入新数组的空闲区。理解这张图你就理解了动态数组的全部精髓。3. 数组的经典应用场景与算法思想3.1 双指针技巧有序数组的精简艺术1.9节一上来就是双指针。数组天然适合双指针因为它支持O(1)的随机访问两个指针可以在一次遍历内完成很多看似需要嵌套循环的任务。我最常用的三个场景两数之和有序数组版本。给定一个升序排列的数组和一个目标值找到两个数使它们的和等于目标值。暴力做法是O(n^2)双重循环双指针的做法是左指针指向开头右指针指向末尾计算当前和。如果和大于目标值右指针左移如果和小于目标值左指针右移如果相等就找到了答案。两个指针最多走完整数组一遍时间复杂度O(n)。移除重复元素。要求原地修改数组让每个元素只出现一次。做法是快慢指针快指针负责探索整个数组慢指针负责维护去重后数组的末尾位置。每当快指针遇到一个与慢指针指向位置不同的元素就把它复制到慢指针的下一个位置同时慢指针前进。最终慢指针的位置就是新数组的长度。容器盛水问题。这是双指针里偏难的一道题核心在于每次移动高度较矮的那一侧指针因为面积受矮的一侧制约。这个问题的证明要看懂移动较矮侧不会错过最优解这一点我在笔记里用了具体的实例展开推导花了不少篇幅。双指针之所以好用源于一个简单事实数组是有序的或可以排序指针移动方向是单调的不会回退所以不会重复计算也不会遗漏。这个单调性是理解双指针解题正确性的关键。3.2 前缀和与差分数组区间问题的杀手锏如果说双指针是面向前向遍历的优化前缀和就是面向区间查询的优化。定义很简单pre[i]表示数组前i个元素的和。有了pre数组查询区间[l, r]的和只需要pre[r1] - pre[l]一次减法搞定时间复杂度O(1)。如果没有前缀和每次查询都要重头遍历区间假设有m次查询、数组长度n总时间复杂度是O(m*n)。一旦n和m都到10^5级别运算量就到10^10了程序基本卡死。用前缀和后预处理O(n) 查询O(1)整体O(nm)这是数量级的提升。我举个例子。你有一个每日销售额数组要频繁回答从第3天到第7天总共卖了多少。直接算当然可以但如果是2000个这样的问题就得循环2000次。前缀和的做法是先把pre[i] pre[i-1] arr[i]准备好每个问题变成pre[7] - pre[2]快得离谱。差分数组则跟前缀和刚好是逆运算。它的应用场景是区间修改给某个区间的所有元素同时加一个值最后再求整个数组被改成了什么样。朴素做法是每次遍历区间加值m次操作就是O(m*n)。差分数组的做法是维护一个diff数组区间[l, r]加val时只做diff[l] valdiff[r1] - val所有区间更新完后再做一次前缀和恢复出目标数组。整个流程O(mn)。这两个数据结构放在一起学特别有意思它们反映了一种空间换时间的思维用O(n)的额外存储把高频重复计算变成常量时间的查表。这种思维方式不仅写算法题有用日常处理日志聚合、时间段统计、报表生成时也经常用到。3.3 数组是哈希表的亲爹哈希冲突处理剖析很多人没有意识到哈希表HashMap、dict的底层就是数组。哈希表的存储主体是一个数组每个数组元素称为桶bucket键通过哈希函数映射到某个桶的下标值就存在那个桶里。哈希冲突是必然要处理的问题。主流方案有两种链地址法和开放寻址法。链地址法就是数组每个桶挂一条链表冲突的元素挂在同一条链上Java里当链表过长时还会转成红黑树就是为了把最坏情况从O(n)降到O(log n)。开放寻址法则是在冲突时向后探查空位Python的dict用的就是改良后的开放寻址法。这跟数组笔记有什么关系关系太大了。正因为数组支持O(1)的随机访问哈希表才能做到O(1)的平均查找时间。当你理解了哈希函数算出下标 → 数组访问对应桶 → 处理冲突这条链路你就不会再疑惑为什么自定义对象的hashCode和equals要一起重写也不会在分析哈希表性能时一头雾水。我在笔记里建议所有学数组的人把哈希表的实现思路自己写一遍哪怕是伪代码也好。很多知识只有当你意识到数组下标其实是个可以直接寻址的索引时才会真正打通。4. 数组实操中的常见问题与排查技巧4.1 值得反复强调的是边界数组越界的隐蔽性数组越界是最常见也最麻烦的运行时错误。在C/C里越界不会报错而是直接访问了相邻内存这在工程上可能造成数据篡改、程序崩溃甚至安全漏洞。Python和Java会抛出异常但这类异常一旦在生产环境出现通常意味着前面的逻辑已经有了漏洞。我总结了几条防越界的实操经验循环变量初始值设为0循环条件写成i n不要写成i n。凡是涉及i1、i-1的下标操作先确认当前i的范围边界。二维数组遍历时优先用外层行、内层列的顺序并且逐层检查行列越界。用切片操作时明确切片的区间语义比如Python的arr[a:b]是左闭右开包含a不包含b写错了会silently返回空结果而不是报错。记忆技巧是数组下标的合法范围永远从0开始到长度减1为止。把这个结论刻在肌肉记忆里很多问题能避免一大半。4.2 拷贝陷阱浅拷贝与深拷贝数组拷贝也是个重灾区。很多人以为arr2 arr1就是拷贝实际上这只是把arr2指向了同一个数组对象修改任何一个都会影响另一个。真正的拷贝方式取决于语言和需求C语言用memcpy逐字节拷贝或者写循环逐个赋值。JavaArrays.copyOf和System.arraycopy是浅拷贝元素是引用时只拷贝引用clone()同理要深拷贝得自己遍历并逐个new对象。Pythonnew_list old_list[:]是浅拷贝copy.deepcopy(old_list)才是深拷贝。Cstd::vector的拷贝构造函数是深拷贝但元素本身是否深拷贝取决于元素类型。在写回溯算法、动态规划状态复制时浅拷贝和深拷贝的区别尤其要命。我踩过一次坑状态数组只做了浅拷贝结果修改新数组时把原数组也改了回溯逻辑直接全乱。从那之后我每次复制数组都会先问自己一句里面的元素是基本类型还是对象如果是对象我需要共享引用还是独立副本4.3 面试/笔试中的数组高频题型清单笔记最后整理了一份练习题清单我这里按难度分类列一下方便自查难度题型核心考察点基础移除元素、去重排序双指针、原地操作基础最大子数组和动态规划、前缀和变体中等旋转数组、矩阵转置下标映射、规律发现中等合并两个有序数组从后向前双指针中等前缀和区间查询前缀和预处理进阶盛最多水的容器双指针、移动矮侧推导进阶差分数组区间更新差分、批量修改这些题目绕不开两个共同能力一是把问题抽象成下标之间的关系二是控制好遍历过程中的边界。说白了数组题考的就是你能否在连续内存的思维框架里熟练地操控下标、边界和区间。从我个人的刷题和工程实践来看数组刷题不要贪多吃透每一种题型背后的一两个标准解法就够了。比如双指针你只要真正理解移动条件为什么成立就能迁移到十几道题上前缀和只要理解预处理换查询速度的思想很多区间问题都能一套思路带过。5. 我的学习建议数组笔记怎么用最见效这套笔记1.7到1.9本身是按照底层基础 → 操作复杂度 → 应用场景 → 踩坑总结的顺序组织的我建议你也按这个顺序消化不要跳着看。底层模型是地基不搞懂下标和内存的关系后面所有边界判断都是空中楼阁。操作复杂度决定了你要不要优化、有没有优化的必要学完这个你才会明白为什么有时候看起来很笨的方法反而是最优解。看的时候动手写代码。每个操作比如插入、删除、扩容、切片都自己实现一遍哪怕是造轮子也没关系。我自己的经验是只看不动手过一周再回头就连双指针的移动条件都记不清了。写一遍跑通再故意写错几个边界条件观察报错和输出差异这个印象能保持很久。最后一个小技巧给数组相关题目准备一个环境清单也就是把语言里数组切片的语法、越界行为的差异、动态扩容的触发条件列在一起。遇到具体语言写代码前先扫一眼清单能节省不少查文档的时间。数组是整个数据结构大厦的第一块砖也是最需要被理解透的一块砖。把这些内容吃透后面学链表、栈、队列、哈希表都能举一反三。毕竟很多高级数据结构的底层最后还是一段连续的内存——一个老老实实的数组。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
