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

1. 暴力解法思路：枚举所有可能的子数组，计算每个子数组的和并取最大值，时间复杂度O(n²)，无法处理大规模数据

2. 前缀和优化思路：

   • 利用前缀和将子数组和转化为两个前缀和的差值

   • 子数组[i,j]的和 = pre_sum[j+1] - pre_sum[i]

   • 在遍历过程中，对于每个位置j，只需要找到之前最小的前缀和，就能得到以j结尾的最大子数组和

3. 关键策略优势：

   • 一次遍历即可完成计算，时间复杂度O(n)

   • 空间复杂度O(1)，只维护必要的前缀和变量

   • 通过动态维护最小前缀和，避免了存储所有前缀和的开销

4. 具体实现：

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

56. 合并区间

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=itemgetter(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

1. 初步思路标题：暴力合并思路

   • 两两检查区间是否重叠，合并后继续检查，时间复杂度高且实现复杂

2. 排序+一次遍历优化思路：

   • 按照区间左端点排序，保证遍历时区间按起始位置有序

   • 排序后，只需检查当前区间是否与结果中最后一个区间重叠

   • 如果重叠则更新右端点，否则直接加入结果集

3. 关键策略优势：

   • 排序后只需一次遍历，时间复杂度O(nlogn)

   • 空间复杂度O(n)，用于存储结果

   • 避免了复杂的多重循环和递归合并

4. 具体实现：

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 按区间左端点排序
        intervals.sort(key=itemgetter(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

189. 轮转数组

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k = k % len(nums)
        nums[:] = nums[-k:] + nums[:-k]

1. 初步思路标题：辅助数组法

   • 使用额外数组存储轮转后的结果，再复制回原数组

   • 需要O(n)额外空间，不符合原地修改的要求

2. 数组切片技巧优化思路：

   • 利用Python的切片特性，可以直接构造轮转后的数组

   • 将原数组分为两部分：后k个元素和前n-k个元素

   • 通过切片拼接后整体赋值给原数组，实现原地修改

3. 关键策略优势：

   • 代码极其简洁，一行实现核心逻辑

   • 时间复杂度O(n)，空间复杂度O(1)（切片操作会创建新列表，但Python内部优化了赋值）

   • 通过取模运算处理k大于数组长度的情况

4. 具体实现：

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

1. 初步思路标题：左右乘积列表法

   • 分别计算每个元素左边所有数的乘积和右边所有数的乘积

   • 需要两个辅助数组存储左右乘积，空间复杂度O(n)

2. 空间优化思路：

   • 先用输出数组suf存储每个元素右边所有数的乘积

   • 再用一个变量pre动态维护左边所有数的乘积

   • 遍历过程中直接更新suf数组为最终结果

3. 关键策略优势：

   • 空间复杂度优化到O(1)（输出数组不计入）

   • 只需两次遍历，时间复杂度O(n)

   • 通过动态维护前缀积，避免了额外数组的开销

4. 具体实现：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # 初始化suf数组，用于存储后缀乘积
        suf = [1] * n
        
        # 第一次遍历：计算每个位置的后缀乘积
        # suf[i]表示nums[i+1]到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 suf

41. 缺失的第一个正数

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. 初步思路标题：哈希表法

   • 使用哈希集合存储所有出现过的正整数，然后从1开始检查

   • 需要O(n)额外空间，不满足常数空间的要求

2. 原地哈希优化思路：

   • 利用数组本身作为哈希表，将每个正整数x放到索引x-1的位置

   • 只关心范围[1, n]内的数，超出此范围的数不影响结果

   • 通过交换操作将每个数放到正确位置，最终第一个位置不对应的索引即为答案

3. 关键策略优势：

   • 空间复杂度O(1)，只使用了原数组进行原地交换

   • 每个元素最多被交换一次，时间复杂度O(n)

   • 巧妙利用数组索引与数值的对应关系，避免额外数据结构

4. 具体实现：

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都在正确位置上，则缺失的是n+1
        return n + 1