导出为pdf，jupyter nbconvert --to html 数组.ipynb¶

数组的 3 句话核心¶

1. 数组 = 同类型元素在一整块连续内存 → 计算地址 = 起始地址 + index × 元素大小，随机访问 O(1)。

2. Python 真正的“连续数组”：array.array('i')、bytes/bytearray、memoryview、numpy.ndarray； Python list 只是连续的 指针槽位，元素对象本身散落各处。

3. 优势与代价：

   • 连续存储带来高速缓存友好、随机访问快；
   • 长度固定，插入/删除需搬迁数据，扩容需整块重拷。

In [ ]:

a = [1001, 1003, 1002, 1004, 1005]

for i, v in enumerate(a):
    print(f"Index: {i}, id: {id(a[i])}")
    """
Index: 0, id: 1710100011344
Index: 1, id: 1710100019536
Index: 2, id: 1710100018608
Index: 3, id: 1710100012880
Index: 4, id: 1710100015696
"""

a = [1001, 1003, 1002, 1004, 1005] for i, v in enumerate(a): print(f"Index: {i}, id: {id(a[i])}") """ Index: 0, id: 1710100011344 Index: 1, id: 1710100019536 Index: 2, id: 1710100018608 Index: 3, id: 1710100012880 Index: 4, id: 1710100015696 """

最大子数组和（LeetCode 53）¶

给定整数数组 nums，求连续子数组（至少包含一个元素）的 最大和

动态规划解法¶

Kadane 算法一步步（介于“太短”与“太长”之间）

1. 设两个变量

   • cur：必须以当前下标 i 结尾的最佳子数组和
   • ans：到目前为止出现过的最大子数组和

2. 遍历数组 对每个元素 x = nums[i]：

   • 若 cur 之前的累加反而拖后腿（cur < 0），就 重新开张：cur = x
   • 否则 继续扩张：cur += x

3. 同步更新全局最优 ans = max(ans, cur) —— 任何时刻都记录历史最高分。

4. 结束即答案 一趟扫完，ans 就是所求最大子数组和。

复杂度：只用常数级变量，时间 O(n)，空间 O(1)。

这样既知道 为什么要断开重开（负前缀只会降低后续和），又明白 如何实现（两行更新），核心思想与实现步骤一目了然。

In [ ]:

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur = ans = nums[0]
        for x in nums[1:]:
            # 局部最优：续攒 or 重新开始
            cur = x if cur + x < x else cur + x
            # 全局最优
            ans = ans if ans >= cur else cur
        return ans 
    
a = [10, -11, -6, 17, -10, -10, 12]
b = Solution()
print(b.maxSubArray(a))

from typing import List class Solution: def maxSubArray(self, nums: List[int]) -> int: cur = ans = nums[0] for x in nums[1:]: # 局部最优：续攒 or 重新开始 cur = x if cur + x < x else cur + x # 全局最优 ans = ans if ans >= cur else cur return ans a = [10, -11, -6, 17, -10, -10, 12] b = Solution() print(b.maxSubArray(a))

In [4]:

from typing import List
class Solution:
    "核心思想——“如果当前累加的和变成了负数，就抛弃它”，复杂度O（n）"
    def maxSubArray(self, nums: List[int]) -> int:
        max_score = cur_score = nums[0]
        for i in range(1, len(nums)):
            if cur_score < 0:
                cur_score = nums[i]
            else:
                cur_score += nums[i]
            max_score = max(max_score, cur_score)
        return max_score
    
a = [10, -11, -6, 17, -10, -10, 12]
b = Solution()
print(b.maxSubArray(a))

from typing import List class Solution: "核心思想——“如果当前累加的和变成了负数，就抛弃它”，复杂度O（n）" def maxSubArray(self, nums: List[int]) -> int: max_score = cur_score = nums[0] for i in range(1, len(nums)): if cur_score < 0: cur_score = nums[i] else: cur_score += nums[i] max_score = max(max_score, cur_score) return max_score a = [10, -11, -6, 17, -10, -10, 12] b = Solution() print(b.maxSubArray(a))

17

合并区间（LeetCode 56）¶

单指针思维

给定区间集合 [1 , 3] , [2 , 6] , [8 , 10] , [15 , 18]。 已按左端点从小到大排序，下面按步骤合并。

1. 初始化

   • 把 intervals[0] = [1, 3] 加入答案，作为当前正在合并的区间。
   • 现在 合并区间 = [1 , 3]。

2. 处理 intervals[1] = [2, 6]

   • 左端点 2 ≤ 3，与当前区间重叠 → 可合并。
   • 更新右端点：max(3, 6) = 6
   • 合并区间变为 [1 , 6]（左端点无需改动）。

3. 处理 intervals[2] = [8, 10]

   • 左端点 8 > 6，与当前区间不重叠 → 不能合并。
   • [1 , 6] 已确定，加入答案；开始新的合并区间 [8 , 10]。

4. 处理 intervals[3] = [15, 18]

   • 左端点 15 > 10，仍不重叠。
   • [8 , 10] 固定并加入答案；最后把 [15 , 18] 作为新合并区间加入。

最终结果¶

[[1, 6], [8, 10], [15, 18]]

In [ ]:

In [ ]:

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

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda p: p[0])  # 按照左端点从小到大排序
        ans = [intervals[0]] #
        for p in intervals[1:]:
            if p[0] <= ans[-1][1]:  # 可以合并
                ans[-1][1] = max(ans[-1][1], p[1])  # 更新右端点最大值
            else:  # 不相交，无法合并
                ans.append(p)  # 新的合并区间
        return ans

from typing import List class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda p: p[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 class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda p: p[0]) # 按照左端点从小到大排序 ans = [intervals[0]] # for p in intervals[1:]: if p[0] <= ans[-1][1]: # 可以合并 ans[-1][1] = max(ans[-1][1], p[1]) # 更新右端点最大值 else: # 不相交，无法合并 ans.append(p) # 新的合并区间 return ans

轮转数组（LeetCode189）¶

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

1.把整个数组反转

2.反转前 k 个元素

3.反转后 n-k 个元素，三次反转即可把后 k 个元素移到前面，实现向右轮转。

In [17]:

from typing import List
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        nums[:] = nums[-k:] + nums[:-k]

from typing import List class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) k = k % n nums[:] = nums[-k:] + nums[:-k]

In [ ]:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k%n

        def reverse(left, right):
            right = right - 1
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        reverse(0, n)
        reverse(0, k)
        reverse(k, n)

class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) k = k%n def reverse(left, right): right = right - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1 reverse(0, n) reverse(0, k) reverse(k, n)

除以自身以外数组的乘积（LeetCode 238）¶

核心思想： 用“前缀积 × 后缀积”替代除法。对每个下标 i，答案是 nums 左边所有元素乘积（前缀积）与右边所有元素乘积（后缀积）的乘积。

---

关键步骤¶

1. 初始化

   • L, R：分别存放前缀积、后缀积，首尾元素先置 1。
   • ans：结果数组，先全部置 1。

2. 计算前缀积 L

   for i in range(1, length):
       L[i] = L[i-1] * nums[i-1]
   

   L[i] 保存 nums[0]…nums[i-1] 的乘积。

3. 计算后缀积 R

   for i in range(length-1, 0, -1):
       R[i-1] = R[i] * nums[i]
   

   R[i] 保存 nums[i+1]…nums[-1] 的乘积。

4. 合并得到答案

   for i in range(length):
       ans[i] = L[i] * R[i]
   

   对每个位置 i，将对应的前缀积与后缀积相乘即得所需结果。

---

复杂度分析

• 时间：O(n) —— 三趟线性遍历。
• 空间：O(n) —— 额外使用 L、R、ans 三个同长度数组。（可通过原地复用将空间优化到 O(1) 额外开销，但思路不变）

In [ ]:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        ans, L, R = [1]*length, [1]*length, [1]*length
        for i in range(1,length):
            L[i] = nums[i-1] * L[i-1]
        
        for i in range(length-1,0,-1):
            R[i-1] = nums[i] * R[i]
        
        for i in  range(length):
            ans[i] = L[i] * R[i]
        
        return ans

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: length = len(nums) ans, L, R = [1]*length, [1]*length, [1]*length for i in range(1,length): L[i] = nums[i-1] * L[i-1] for i in range(length-1,0,-1): R[i-1] = nums[i] * R[i] for i in range(length): ans[i] = L[i] * R[i] return ans

思路升级：用输出数组本身存前缀积，再用一个常量变量滚动后缀积¶

• 首扫：顺序遍历，把 i 左侧元素乘积直接写进 ans[i]。

• 次扫：逆序遍历，用变量 R 累乘右侧元素；边更新 R 边把结果乘回 ans[i]。 这样只额外用到一个整数 R，把额外空间降到 O(1)（题目默认不计输出数组）。

• 相当于把ans作为原来的左缀积L，而R实时更新，从右到左，直接乘到ans上

---

复杂度

• 时间：两次线性遍历 → O(n)
• 空间：只用常量 suffix → O(1) 额外空间（不含输出数组）

In [ ]:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n

        # 前缀积：i 从 1 开始，跳过 0
        for i in range(1, n):
            ans[i] = ans[i-1] * nums[i-1]

        # 后缀积：i 从 n-1 到 0，必须含 0
        R = 1
        for i in range(n-1, -1, -1):
            ans[i] *= R    # 先用
            R *= nums[i]   # 再乘

        return ans

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) ans = [1] * n # 前缀积：i 从 1 开始，跳过 0 for i in range(1, n): ans[i] = ans[i-1] * nums[i-1] # 后缀积：i 从 n-1 到 0，必须含 0 R = 1 for i in range(n-1, -1, -1): ans[i] *= R # 先用 R *= nums[i] # 再乘 return ans

缺失的第一个正数¶

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

原地哈希法核心思想¶

将数组本身当作哈希表，用索引位置表示数字，用符号表示该数字是否存在

• 索引 i 代表数字 i+1
• 负数表示该位置对应的数字存在
• 正数表示该位置对应的数字不存在

关键注意点¶

1. 符号处理¶

• 读取时：必须用 abs(nums[i]) 获取原始数值
• 标记时：用 -abs(nums[num-1]) 确保变为负数，避免重复标记

2. 边界控制¶

• 范围检查：只处理 1 ≤ num ≤ n 的数字
• 预处理：将 n+1 作为占位符，因为它不会影响 [1,n] 的标记

3. 映射关系¶

• 数字 x → 索引 x-1
• 索引 i → 数字 i+1

举例演示¶

原数组: [3, 4, -1, 1]  (n=4)

步骤1: [3, 4, 5, 1]     # -1改为5
步骤2: 
  - 看到3，标记索引2：[3, 4, -5, 1]
  - 看到4，标记索引3：[3, 4, -5, -1]  
  - 看到5，超出范围，跳过
  - 看到1，标记索引0：[-3, 4, -5, -1]
步骤3: 索引1为正数，返回 1+1 = 2

核心优势：O(1) 空间复杂度，充分利用数组索引和符号的双重信息。

In [2]:

class Solution:
    def firstMissingPositive(self, nums):
        hashtable = set(nums)
        n = len(nums)
        for i in range(1, n+2):
            if i not in hashtable:
                return i

class Solution: def firstMissingPositive(self, nums): hashtable = set(nums) n = len(nums) for i in range(1, n+2): if i not in hashtable: return i

In [ ]:

def firstMissingPositive(nums):
    n = len(nums)
    
    # 第一步：将所有非正数和大于n的数改为n+1
    # 这样确保数组中只有[1,n+1]范围内的数
    for i in range(n):
        if nums[i] <= 0:
            nums[i] = n + 1
    
    # 第二步：利用符号标记存在性
    # 对于数字x，将索引x-1位置的数字标记为负数
    for i in range(n):
        num = abs(nums[i]) #因为下面的操作会将nums[i]的值由正变负，所以需要取绝对值
        if num <= n:
            nums[num - 1] = -abs(nums[num - 1])
    
    # 第三步：找到第一个正数的位置
    for i in range(n):
        if nums[i] > 0:
            return i + 1
    
    # 如果所有位置都被标记了，说明[1,n]都存在
    return n + 1

def firstMissingPositive(nums): n = len(nums) # 第一步：将所有非正数和大于n的数改为n+1 # 这样确保数组中只有[1,n+1]范围内的数 for i in range(n): if nums[i] <= 0: nums[i] = n + 1 # 第二步：利用符号标记存在性 # 对于数字x，将索引x-1位置的数字标记为负数 for i in range(n): num = abs(nums[i]) #因为下面的操作会将nums[i]的值由正变负，所以需要取绝对值 if num <= n: nums[num - 1] = -abs(nums[num - 1]) # 第三步：找到第一个正数的位置 for i in range(n): if nums[i] > 0: return i + 1 # 如果所有位置都被标记了，说明[1,n]都存在 return n + 1