Leetcode Top100答案和解释 -- Python版本（普通数组）

53. 最大子数组和class Solution: def maxSubArray(self, nums: List[int]) - int: ans -inf min_pre_sum pre_sum 0 for x in nums: pre_sum x ans max(ans, pre_sum - min_pre_sum) min_pre_sum min(min_pre_sum, pre_sum) return ans暴力解法思路枚举所有可能的子数组计算每个子数组的和并取最大值时间复杂度O(n²)无法处理大规模数据前缀和优化思路利用前缀和将子数组和转化为两个前缀和的差值子数组[i,j]的和 pre_sum[j1] - pre_sum[i]在遍历过程中对于每个位置j只需要找到之前最小的前缀和就能得到以j结尾的最大子数组和关键策略优势一次遍历即可完成计算时间复杂度O(n)空间复杂度O(1)只维护必要的前缀和变量通过动态维护最小前缀和避免了存储所有前缀和的开销具体实现class Solution: def maxSubArray(self, nums: List[int]) - int: ans -inf # 初始化答案为负无穷 min_pre_sum pre_sum 0 # 最小前缀和和当前前缀和 for x in nums: pre_sum x # 更新当前前缀和 # 当前前缀和减去之前的最小前缀和得到以当前位置结尾的最大子数组和 ans max(ans, pre_sum - min_pre_sum) # 更新最小前缀和为后续位置做准备 min_pre_sum min(min_pre_sum, pre_sum) return ans56. 合并区间class Solution: def merge(self, intervals: List[List[int]]) - List[List[int]]: intervals.sort(keyitemgetter(0)) ans [] for p in intervals: if ans and p[0] ans[-1][1]: ans[-1][1] max(ans[-1][1], p[1]) else: ans.append(p) return ans初步思路标题暴力合并思路两两检查区间是否重叠合并后继续检查时间复杂度高且实现复杂排序一次遍历优化思路按照区间左端点排序保证遍历时区间按起始位置有序排序后只需检查当前区间是否与结果中最后一个区间重叠如果重叠则更新右端点否则直接加入结果集关键策略优势排序后只需一次遍历时间复杂度O(nlogn)空间复杂度O(n)用于存储结果避免了复杂的多重循环和递归合并具体实现class Solution: def merge(self, intervals: List[List[int]]) - List[List[int]]: # 按区间左端点排序 intervals.sort(keyitemgetter(0)) ans [] for p in intervals: # 如果结果非空且当前区间与最后一个区间重叠 if ans and p[0] ans[-1][1]: # 合并区间更新右端点为较大值 ans[-1][1] max(ans[-1][1], p[1]) else: # 不重叠直接加入结果集 ans.append(p) return ans189. 轮转数组class Solution: def rotate(self, nums: List[int], k: int) - None: k k % len(nums) nums[:] nums[-k:] nums[:-k]初步思路标题辅助数组法使用额外数组存储轮转后的结果再复制回原数组需要O(n)额外空间不符合原地修改的要求数组切片技巧优化思路利用Python的切片特性可以直接构造轮转后的数组将原数组分为两部分后k个元素和前n-k个元素通过切片拼接后整体赋值给原数组实现原地修改关键策略优势代码极其简洁一行实现核心逻辑时间复杂度O(n)空间复杂度O(1)切片操作会创建新列表但Python内部优化了赋值通过取模运算处理k大于数组长度的情况具体实现class Solution: def rotate(self, nums: List[int], k: int) - None: # 处理k大于数组长度的情况 k k % len(nums) # 切片拼接并整体赋值给原数组 nums[:] nums[-k:] nums[:-k]238. 除自身以外数组的乘积class Solution: def productExceptSelf(self, nums: List[int]) - List[int]: n len(nums) suf [1] * n for i in range(n - 2, -1, -1): suf[i] suf[i 1] * nums[i 1] pre 1 for i, x in enumerate(nums): suf[i] * pre pre * x return suf初步思路标题左右乘积列表法分别计算每个元素左边所有数的乘积和右边所有数的乘积需要两个辅助数组存储左右乘积空间复杂度O(n)空间优化思路先用输出数组suf存储每个元素右边所有数的乘积再用一个变量pre动态维护左边所有数的乘积遍历过程中直接更新suf数组为最终结果关键策略优势空间复杂度优化到O(1)输出数组不计入只需两次遍历时间复杂度O(n)通过动态维护前缀积避免了额外数组的开销具体实现class Solution: def productExceptSelf(self, nums: List[int]) - List[int]: n len(nums) # 初始化suf数组用于存储后缀乘积 suf [1] * n # 第一次遍历计算每个位置的后缀乘积 # suf[i]表示nums[i1]到nums[n-1]的乘积 for i in range(n - 2, -1, -1): suf[i] suf[i 1] * nums[i 1] # 第二次遍历动态维护前缀乘积并更新结果 pre 1 # 前缀乘积 for i, x in enumerate(nums): # 当前位置的结果 前缀乘积 × 后缀乘积 suf[i] * pre # 更新前缀乘积为下一位置做准备 pre * x return suf41. 缺失的第一个正数class Solution: def firstMissingPositive(self, nums: list[int]) - int: n len(nums) for i in range(n): while 1 nums[i] n and nums[nums[i] - 1] ! nums[i]: j nums[i] - 1 nums[i], nums[j] nums[j], nums[i] for i in range(n): if nums[i] ! i 1: return i 1 return n 1初步思路标题哈希表法使用哈希集合存储所有出现过的正整数然后从1开始检查需要O(n)额外空间不满足常数空间的要求原地哈希优化思路利用数组本身作为哈希表将每个正整数x放到索引x-1的位置只关心范围[1, n]内的数超出此范围的数不影响结果通过交换操作将每个数放到正确位置最终第一个位置不对应的索引即为答案关键策略优势空间复杂度O(1)只使用了原数组进行原地交换每个元素最多被交换一次时间复杂度O(n)巧妙利用数组索引与数值的对应关系避免额外数据结构具体实现class Solution: def firstMissingPositive(self, nums: list[int]) - int: n len(nums) # 第一次遍历将每个在[1, n]范围内的数放到正确的位置上 for i in range(n): # 当当前数在[1, n]范围内且不在正确位置上时进行交换 while 1 nums[i] n and nums[nums[i] - 1] ! nums[i]: j nums[i] - 1 # 目标位置 nums[i], nums[j] nums[j], nums[i] # 交换到正确位置 # 第二次遍历找出第一个不在正确位置上的数 for i in range(n): if nums[i] ! i 1: return i 1 # 如果1到n都在正确位置上则缺失的是n1 return n 1