数组与字符串

本章目标：掌握数组的核心操作技巧——双指针、前缀和、差分，以及字符串匹配基础。

你将学到

• 数组的内存连续性与随机访问特性
• 双指针反转与原地操作
• 前缀和与差分数组
• 二维数组的遍历技巧
• 字符串匹配算法（KMP、Rabin-Karp）
• 旋转数组与区间操作

1. 概念

数组是最基本的数据结构，在内存中连续存储，支持 O(1) 随机访问。字符串本质上就是字符数组。Swift 中 Array 和 String 都是值类型，但底层对拷贝做了写时优化（Copy-on-Write）。

数组的核心优势是随机访问，核心劣势是中间插入/删除需要移动元素（O(n)）。因此大量数组算法的核心思路是：用指针技巧避免频繁移动元素。

2. 核心模板

双指针反转

// 原地反转数组，时间 O(n)，空间 O(1)
func reverse<T>(_ arr: inout [T], _ left: Int, _ right: Int) {
    var l = left, r = right
    while l < r {
        arr.swapAt(l, r)
        l += 1
        r -= 1
    }
}

前缀和

// 构建前缀和，支持 O(1) 区间求和
// prefix[i] = arr[0] + arr[1] + ... + arr[i-1]
// 区间 [l, r) 的和 = prefix[r] - prefix[l]
func prefixSum(_ arr: [Int]) -> [Int] {
    var prefix = [Int](repeating: 0, count: arr.count + 1)
    for i in 0..<arr.count {
        prefix[i + 1] = prefix[i] + arr[i]
    }
    return prefix
}

// 查询区间 [l, r]（闭区间）的元素和
func rangeSum(_ prefix: [Int], _ l: Int, _ r: Int) -> Int {
    return prefix[r + 1] - prefix[l]
}

差分数组

// 对区间 [l, r] 批量加 val，最后还原原数组
// diff[l] += val, diff[r+1] -= val
func diff(_ arr: [Int], _ updates: [(l: Int, r: Int, val: Int)]) -> [Int] {
    var diff = [Int](repeating: 0, count: arr.count + 1)
    for (l, r, val) in updates {
        diff[l] += val
        diff[r + 1] -= val
    }
    var result = [Int](repeating: 0, count: arr.count)
    var cur = 0
    for i in 0..<arr.count {
        cur += diff[i]
        result[i] = arr[i] + cur
    }
    return result
}

复杂度

• 双指针反转：时间 O(n)，空间 O(1)
• 前缀和：预处理 O(n)，查询 O(1)
• 差分数组：更新 O(1)，还原 O(n)

3. 经典题目精讲

LeetCode 1 · 两数之和

题意：给定数组和目标值，返回两个元素的下标，使它们之和等于目标值。

思路：暴力两重循环 O(n²)。用哈希表记录已遍历的值与下标，每次查 target - num 是否在表中，降为 O(n)。

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var map: [Int: Int] = [:]  // 值 -> 下标
    for (i, num) in nums.enumerated() {
        let complement = target - num
        if let j = map[complement] {
            return [j, i]
        }
        map[num] = i
    }
    return []
}

LeetCode 11 · 盛最多水的容器

题意：数组中每个元素代表高度，求两条线与 x 轴围成的最大水量。

思路：对撞指针从两端向中间逼近，每次移动较短的一边（因为移动较长的一边不可能获得更大面积）。

func maxArea(_ height: [Int]) -> Int {
    var left = 0, right = height.count - 1
    var maxWater = 0
    while left < right {
        let h = min(height[left], height[right])
        let w = right - left
        maxWater = max(maxWater, h * w)
        if height[left] < height[right] {
            left += 1
        } else {
            right -= 1
        }
    }
    return maxWater
}

LeetCode 42 · 接雨水

题意：给定非负整数数组表示柱子高度，求能接住多少雨水。

思路：每个位置能接的雨水量 = min(左边最大值, 右边最大值) - 自身高度。双指针法可 O(1) 空间解决。

func trap(_ height: [Int]) -> Int {
    if height.isEmpty { return 0 }
    var left = 0, right = height.count - 1
    var leftMax = 0, rightMax = 0
    var water = 0
    while left < right {
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                water += leftMax - height[left]
            }
            left += 1
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                water += rightMax - height[right]
            }
            right -= 1
        }
    }
    return water
}

4. 易错点

• ⚠️ 前缀和数组长度是 n+1，注意越界
• ⚠️ 差分数组更新时 diff[r+1] 可能越界，需要数组长度为 n+1
• ⚠️ Swift 中 String 不能像数组那样用下标随机访问，需转 [Character] 或使用 string.index
• ⚠️ 旋转数组时注意 k 可能大于数组长度，需要取模

5. 推荐刷题清单

题号	题名	难度	关键
1	两数之和	Easy	哈希表
11	盛最多水的容器	Medium	对撞指针
15	三数之和	Medium	排序 + 双指针
42	接雨水	Hard	双指针/单调栈
209	长度最小的子数组	Medium	滑动窗口/前缀和
238	除自身以外数组的乘积	Medium	前缀积
41	缺失的第一个正数	Hard	原地哈希

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS)