Array 基础Array 是一块连续的内存空间用来存储一组相同类型的数据。创建nums [1, 2, 3, 4, 5]empty []zeros [0] * 5print(zeros)访问 Access根据 index 获取元素nums [10,20,30,40]print(nums[2])修改元素nums[2] 100print(nums)获取长度 len()nums [1,2,3,4]print(len(nums))添加元素 append()添加一个元素到尾部nums [1,2,3]nums.append(4)print(nums)插入元素 insert()index2的位置插入。nums [1,2,3,4]nums.insert(2,100)print(nums) #[1,2,100,3,4]删除元素pop()删除最后一个nums[1,2,3]xnums.pop()print(x)print(nums)pop(index)删除指定位置nums[10,20,30,40]nums.pop(1)print(nums) # [10,30,40]remove()根据值删除 * 注意只删除第一个匹配值nums[10,20,30]nums.remove(20)print(nums) # [10,30]查找 Searchin查找是否存在nums[1,2,3,4]print(3 in nums) # Trueindex()找位置nums[10,20,30]print(nums.index(20)) #1排序 sort()原地排序nums[3,1,5,2]nums.sort()print(nums) # [1,2,3,5]降序nums.sort(reverseTrue) #[5,3,2,1]反转 reverse()nums[1,2,3]nums.reverse()print(nums) #[3,2,1]切片 slicing左闭右开start index end复制数组copy nums[:]反转nums[::-1]合并a[1,2]b[3,4]cabprint(c) # [1,2,3,4]常见考法看到什么想到什么找是否存在 / 出现次数HashMap / Set有序数组找两个数双指针连续子数组最长/最短滑动窗口子数组和为 K前缀和 HashMap区间重叠排序原地删除/移动快慢指针最大连续和Kadane下一个更大/更小单调栈Top KHeap不能用除法求乘积左右前缀积HashMap 计数 / 查找型核心套路需要快速判断某个数/状态是否出现过就用 HashMap 或 Set。“是否存在”“出现次数”“成对匹配”“去重”“频率最高”需要保持顺序、可以重复→ 用list只关心有没有或者需要去重→ 用setseen {}for i, x in enumerate(nums):need target - xif need in seen:return [seen[need], i]seen[x] i题型代表题套路两数之和Two Sum边遍历边查target - x判断重复Contains Duplicateset去重字母/元素频率Valid AnagramCounter分组Group Anagrams排序后作为 key最长连续序列Longest Consecutive Sequenceset 判断x-1是否存在双指针 Two Pointers核心套路数组有序或者可以从两边夹逼就用双指针。“有序数组”“找两个数”“删除/压缩数组”“从两端比较”高频题题型代表题套路两数和 IITwo Sum II左右指针夹逼三数和3Sum排序 固定一个数 双指针盛最多水Container With Most Water移动短板删除重复Remove Duplicates快慢指针移动零Move Zeroes快慢指针接雨水Trapping Rain Water左右最大值 / 双指针left, right 0, len(nums) - 1while left right:cur nums[left] nums[right]if cur target:return [left, right]elif cur target:left 1else:right - 1前缀和 Prefix Sum核心套路频繁求区间和或者问某段 subarray 是否满足条件。“subarray sum”“区间和”“和为 k”“连续子数组”以后看到数组题直接在脑子里问三件事1️⃣ 能不能“左边一个信息”prefix2️⃣ 能不能“右边一个信息”suffix3️⃣ 能不能 O(1) 合并answer[i] left[i] * right[i]不要一看到数组题就想我要不要开 prefix 数组而是先问自己我后面还会不会用到这个状态不会 → 用一个变量维护如 left_sum、prefix、suffix。会而且要按位置访问 → 开 prefix[] / suffix[]。不会按位置访问只关心有没有出现过或出现几次 → 用 HashMap像 LC560。题型代表题套路区间和Range Sum Queryprefix 数组和为 K 的子数组Subarray Sum Equals Kprefix sum hashmap连续数组Contiguous Array把 0 当 -1乘积除自身Product of Array Except Self左右前缀积最大子数组和Maximum SubarrayKadane / 前缀思想经典模板和为 K 的子数组count 0prefix 0seen {0: 1}for x in nums:prefix xcount seen.get(prefix - k, 0)seen[prefix] seen.get(prefix, 0) 1return count第一阶段必须秒懂1480 Running Sum 303 Range Sum724 Pivot Index第二阶段核心套路238 Product Except Self560 Subarray Sum K152 Max Product Subarray第三阶段面试级42 Trapping Rain Water239 Sliding Window Maximum排序 贪心核心套路先排序让局部关系变简单。高频题题型代表题套路合并区间Merge Intervals按 start 排序插入区间Insert Interval分三段处理无重叠区间Non-overlapping Intervals按 end 排序贪心会议室Meeting Rooms排序判断冲突会议室 IIMeeting Rooms II排序 min heap分发饼干Assign Cookies排序 贪心合并区间模板intervals.sort() res [] for start, end in intervals: if not res or start res[-1][1]: res.append([start, end]) else: res[-1][1] max(res[-1][1], end) return res适用信号“区间” “重叠” “会议” “最少数量” “最多安排”原地修改 / 快慢指针核心套路不能额外开数组要求 in-place就用快慢指针。高频题题型代表题套路删除重复元素Remove Duplicates from Sorted Arrayslow 记录有效位置删除指定元素Remove Elementslow 覆盖移动零Move Zeroes非零元素往前放颜色分类Sort Colors三指针下一个排列Next Permutation从右找下降点模板slow 0 for fast in range(len(nums)): if nums[fast] 满足保留条件: nums[slow] nums[fast] slow 1 return slow适用信号“in-place” “O(1) extra space” “remove” “move” “modify nums directly”Top K / Heap核心套路找最大/最小 K 个用 heap。高频题题型代表题第 K 大元素Kth Largest Element前 K 高频元素Top K Frequent Elements数据流中位数Find Median from Data Stream合并 K 个有序链表Merge K Sorted ListsTop K 高频模板from collections import Counter import heapq count Counter(nums) return [x for x, freq in heapq.nlargest(k, count.items(), keylambda p: p[1])]适用信号“top k” “kth largest” “频率最高” “数据流”矩阵矩阵一般混着别的概念考rows len(matrix) cols len(matrix[0])