🔢 数组基础 — 双面夹击与最大子数组

📖 数组的核心概念

数组（Array）是最基础的数据结构，在内存中连续存储相同类型的元素。数组的随机访问时间复杂度为 O(1)，插入/删除需要移动元素，时间复杂度为 O(n)。面试中，数组问题常常结合双指针、哈希表、前缀和等技巧来优化。

1. 数组的常见操作模式

2. Python 数组操作速查

# 初始化
arr = [1, 2, 3, 4, 5]
arr = [0] * 10           # 固定大小

# 访问与修改
x = arr[0]               # O(1) 访问
arr[0] = 10              # O(1) 修改

# 添加与删除
arr.append(6)            # O(1) 均摊
arr.pop()                # O(1) 删除末尾
arr.insert(0, 0)         # O(n) 头部插入
arr.pop(0)               # O(n) 头部删除

# 切片
sub = arr[1:4]           # [arr[1], arr[2], arr[3]]
rev = arr[::-1]          # 反转

# 排序与查找
arr.sort()               # 原地排序 O(n log n)
idx = arr.index(3)       # 查找 O(n)

🎯 题目一：两数之和 (LC 1)

题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，且同一个元素不能使用两遍。

思路分析

代码实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in hash_map:
                return [hash_map[complement], i]
            hash_map[num] = i
        return []

复杂度分析

时间复杂度：O(n) — 只需一次遍历，哈希表查找 O(1)

空间复杂度：O(n) — 最坏情况存入 n-1 个元素

变体练习

• LC 167 两数之和 II（有序数组，可用双指针 O(1) 空间）
• LC 15 三数之和（排序+双指针）
• LC 454 四数相加 II（分组哈希）

🎯 题目二：存在重复元素 (LC 217)

题目描述：给你一个整数数组 nums。如果任一值在数组中出现至少两次，返回 true；如果数组中每个元素互不相同，返回 false。

思路分析

代码实现

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

复杂度分析

时间复杂度：O(n) — 单次遍历 + O(1) 集合操作

空间复杂度：O(n) — 最坏存入 n 个元素

变体练习

• LC 219 存在重复元素 II（限制下标差 ≤ k）
• LC 220 存在重复元素 III（限制值差 ≤ t，下标差 ≤ k，滑动窗口+有序集合）

🎯 题目三：最大子数组和 (LC 53)

题目描述：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路分析

代码实现

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur_sum = best_sum = nums[0]
        for num in nums[1:]:
            cur_sum = max(num, cur_sum + num)
            best_sum = max(best_sum, cur_sum)
        return best_sum

复杂度分析

时间复杂度：O(n) — 一次遍历

空间复杂度：O(1) — 只用两个变量

变体练习

• LC 152 乘积最大子数组（ Kadane 变体，需同时维护最大和最小）
• LC 918 环形子数组最大和（分两种情况讨论）
• LC 53 进阶：如何返回最大子数组的起止位置？

📝 课后练习

1. LC 26 删除有序数组中的重复项（原地双指针）
2. LC 27 移除元素（读写指针）
3. LC 66 加一（数组模拟加法）
4. LC 283 移动零（快慢指针变种）
5. LC 485 最大连续1的个数（简单计数）

🔑 本课要点回顾

• 哈希表可将"查找配对"从 O(n²) 降到 O(n)
• 集合去重是 O(n) 的标准操作，排序去重是 O(n log n) 但省空间
• Kadane 算法：cur = max(num, cur+num)，核心是"负贡献直接丢弃"
• 数组原地修改的关键：用快慢指针分离读写
• 面试时先说暴力解法，再优化，展示思维过程

📚 扩展阅读

• 《算法导论》第4章 分治策略（最大子数组的分治解法）
• 《数据结构与算法分析》数组与链表章节
• Kadane 算法原论文：Kadane, J. B. (1984)
• 可视化：visualgo.net/en/array

🔬 数组的高级技巧

数组看似简单，但面试中的数组题往往暗藏玄机。这里补充几个重要的数组高级技巧，为后续课程做铺垫。

1. 原地哈希

当数组元素范围在 [1, n] 时，可以把数组本身当作哈希表使用。通过将元素值映射到索引（nums[i] → 索引 nums[i]-1），实现 O(1) 空间的检测。

# 原地哈希: 找到所有出现两次的数
# nums[i] 应该在 nums[nums[i]-1] 的位置
def findDuplicates(nums):
    result = []
    for num in nums:
        idx = abs(num) - 1
        if nums[idx] < 0:
            result.append(abs(num))
        else:
            nums[idx] = -nums[idx]
    return result

2. 摩尔投票法

在 O(1) 空间内找多数元素（出现次数 > n/2 的元素）。核心思想：不同元素两两抵消，最后剩下的就是多数元素。

def majorityElement(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate