力扣 Hot100 普通数组题解 Python 实现

一、53. 最大子数组和

• 思路：前缀和优化。维护最小前缀和，避免双重循环。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        res = float('-inf')
        preSum = 0
        minPreSum = 0
        for n in nums:
            preSum += n
            res = max(res, preSum - minPreSum)
            minPreSum = min(minPreSum, preSum)
        return res

• 思路 2：动态规划 (DP)。定义 dp[i] 表示以 nums[i] 结尾的最大子数组和。

class Solution:
    def maxSubArray(self, nums):
        dp = [0] * len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1], 0) + nums[i]
        return max(dp)

二、56. 合并区间

• 思路：先将区间按起始位置排序。遍历区间，若当前区间与结果集最后一个区间有交集则合并，否则添加新区间。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda p: p[0])
        res = []
        for p in intervals:
            if res and p[0] <= res[-1][1]:
                res[-1][1] = max(res[-1][1], p[1])
            else:
                res.append(p)
        return res

三、189. 轮转数组

• 思路：利用反转操作实现原地旋转，注意处理 k 大于数组长度的情况。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def reverse(i, j):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
        
        n = len(nums)
        k %= n
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

四、238. 除自身以外数组的乘积

• 思路：前后缀分解。分别计算每个位置左侧和右侧的乘积。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre = [1] * n
        for i in range(1, n):
            pre[i] = pre[i-1] * nums[i-1]
        suf = [1] * n
        for i in range(n-2, -1, -1):
            suf[i] = suf[i+1] * nums[i+1]
        return [p * s for p, s in zip(pre, suf)]

五、41. 缺失的第一个正数

• 思路：原地哈希。将每个数字放到其值对应的索引位置上（例如值为 1 放在索引 0）。

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]:
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1