一、先想明白为什么要有数组如果没有数组你想存一个班 50 个学生的数学成绩你需要写score185 score292 score378 ... score5066这显然是灾难。数组的诞生就是为了解决「批量存储和访问同类型数据」的问题。它用一个统一的名字数组名代表这一组数据用 ** 下标索引** 来区分每个元素这样你就可以用scores[0]、scores[1]...scores[49]来访问任意一个学生的成绩。二、数组的本质连续的内存空间✅ 核心思想刻在脑子里用一块连续的、固定大小的内存空间换取 O (1) 的随机访问能力。这是数组所有特性的根源也是它和其他所有数据结构最本质的区别。生活化类比数组就像一排连续的酒店房间酒店名字 数组名房间号 数组下标从 0 开始不是 1每个房间只能住同类型的客人比如都是单人房 数组元素类型相同房间是连续的知道第一个房间的门牌号就能直接算出第 N 个房间的门牌号 数组的随机访问关键特性内存连续这是最重要的特性没有之一大小固定创建时必须指定大小之后不能改变元素同类型所有元素占用的内存大小相同三、数组的基本操作与复杂度所有复杂度都可以从「连续内存」这个本质推导出来不需要死记硬背。表格操作时间复杂度为什么从本质推导随机访问查指定下标O(1)直接用公式计算地址元素地址 数组首地址 下标 × 单个元素大小尾部插入 / 删除O(1)不需要移动其他元素中间 / 头部插入 / 删除O(n)插入 / 删除位置后面的所有元素都必须整体往后 / 往前挪一个位置腾出空间查找不知道下标O(n)只能从头开始一个一个找举个例子假设数组[1,2,3,4,5]存在内存中首地址是 100每个 int 占 4 个字节第 0 个元素地址100 0×4 100第 2 个元素地址100 2×4 108现在要在第 2 个位置插入元素 6那么原来的 3、4、5 都要往后挪一个位置一共移动 3 个元素所以时间复杂度是 O (n)四、数组的核心解题思想双指针法数组 90% 的面试题都可以用双指针法解决。这是线性结构数组、链表、字符串通用的核心思想必须彻底掌握。双指针法的本质用两个指针在数组上移动把两层循环的 O (n²) 时间复杂度优化成一层循环的 O (n)。类型 1快慢指针原地修改数组适用场景所有要求 **「原地修改数组」** 的题目不能使用额外的数组空间。核心思想慢指针指向最终结果数组中下一个应该存放元素的位置快指针遍历原数组寻找符合条件的元素当快指针找到符合条件的元素时就把它赋值给慢指针指向的位置然后慢指针向前走一步例题 1LeetCode 283. 移动零题目给定一个数组nums将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。必须在原数组上操作不能拷贝额外的数组。错误思路暴力法遍历数组遇到 0 就把它和后面的元素交换时间复杂度 O (n²)正确思路快慢指针慢指针slow初始化为 0指向结果数组第一个应该放元素的位置快指针fast遍历整个数组当fast遇到非零元素时把nums[fast]赋值给nums[slow]然后slow 1遍历结束后slow之前的所有元素都是非零的把slow之后的所有元素都设为 0逐行解析代码python运行def moveZeroes(nums): :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1 # 测试代码 if __name__ __main__: # 测试用例1 nums1 [0, 1, 0, 3, 12] print(原始数组:, nums1) moveZeroes(nums1) print(移动零后:, nums1) # 测试用例2 nums2 [0] print(\n原始数组:, nums2) moveZeroes(nums2) print(移动零后:, nums2) # 测试用例3 nums3 [1, 2, 3, 4, 5] print(\n原始数组:, nums3) moveZeroes(nums3) print(移动零后:, nums3) # 测试用例4 nums4 [0, 0, 0, 1, 2, 3] print(\n原始数组:, nums4) moveZeroes(nums4) print(移动零后:, nums4) # 测试用例5 nums5 [1, 0, 0, 2, 0, 3, 0, 4, 0] print(\n原始数组:, nums5) moveZeroes(nums5) print(移动零后:, nums5)时间复杂度O (n)只遍历了数组两次空间复杂度O (1)没有使用额外空间举一反三LeetCode 27. 移除元素题目给你一个数组nums和一个值val原地移除所有数值等于val的元素并返回移除后数组的新长度。你会发现这道题和移动零思路完全一样只是第二步不需要了python运行def removeElement(nums, val): :type nums: List[int] :type val: int :rtype: int # 慢指针指向下一个不等于val的元素应该放置的位置 slow 0 # 快指针遍历数组 for fast in range(len(nums)): # 如果当前元素不等于目标值 if nums[fast] ! val: # 将元素移到前面 nums[slow] nums[fast] slow 1 return slow # 测试代码 if __name__ __main__: # 测试用例1 nums1 [3, 2, 2, 3] val1 3 print(f原始数组: {nums1}, 要移除的值: {val1}) new_length removeElement(nums1, val1) print(f新长度: {new_length}) print(f前{new_length}个元素: {nums1[:new_length]}) # 测试用例2 nums2 [0, 1, 2, 2, 3, 0, 4, 2] val2 2 print(f\n原始数组: {nums2}, 要移除的值: {val2}) new_length removeElement(nums2, val2) print(f新长度: {new_length}) print(f前{new_length}个元素: {nums2[:new_length]}) # 测试用例3 nums3 [1, 2, 3, 4, 5] val3 6 print(f\n原始数组: {nums3}, 要移除的值: {val3}) new_length removeElement(nums3, val3) print(f新长度: {new_length}) print(f前{new_length}个元素: {nums3[:new_length]}) # 测试用例4 nums4 [1, 1, 1, 1, 1] val4 1 print(f\n原始数组: {nums4}, 要移除的值: {val4}) new_length removeElement(nums4, val4) print(f新长度: {new_length}) print(f前{new_length}个元素: {nums4[:new_length]}) # 测试用例5 nums5 [] val5 0 print(f\n原始数组: {nums5}, 要移除的值: {val5}) new_length removeElement(nums5, val5) print(f新长度: {new_length}) print(f前{new_length}个元素: {nums5[:new_length] if new_length 0 else []})✅ 记住所有「原地移除数组中特定元素」的题目都是这个模板。类型 2左右指针有序数组适用场景数组是有序的这是前提。核心思想左指针指向数组的开头最左边右指针指向数组的结尾最右边根据两个指针指向元素的和判断应该移动哪个指针例题 2LeetCode 704. 二分查找题目给定一个n个元素有序的升序整型数组nums和一个目标值target写一个函数搜索nums中的target如果目标值存在返回下标否则返回 - 1。为什么二分查找必须用数组因为二分查找需要随机访问中间元素只有数组能做到 O (1) 的随机访问链表做不到。核心思路左指针left初始化为 0右指针right初始化为len(nums)-1计算中间位置mid (left right) // 2如果nums[mid] target找到目标返回mid如果nums[mid] target说明目标在右半部分left mid 1如果nums[mid] target说明目标在左半部分right mid - 1循环结束还没找到返回 - 1逐行解析代码python运行def search(nums, target): left 0 right len(nums) - 1 # 注意右指针指向最后一个元素 while left right: # 注意循环条件是不是 mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1间复杂度O (logn)每次搜索范围缩小一半空间复杂度O(1)✅ 记住只要题目说「数组有序」第一反应就是二分查找。五、数组的典型应用场景存储同类型的一组数据比如学生成绩、商品列表实现其他数据结构的底层栈、队列、哈希表、堆、字符串所有需要随机访问的场景数据量大小已知且查多改少的场景