数组

基础回顾

数组是最基本的数据结构，在内存中是连续存储的。理解数组的内存布局是掌握双指针和滑动窗口的基础。

# 数组基础操作的时间复杂度
arr = [1, 2, 3, 4, 5]

# 随机访问：O(1)
val = arr[2]  # 3

# 查找：O(n)
# 插入/删除：O(n)（需要移动元素）

双指针技巧

双指针是一种常用技巧，通过两个指针在数组上协同移动来解决问题。

1. 对撞指针

两个指针分别从两端向中间移动，常用于有序数组的查找。

示例：两数之和 II（有序数组）

def two_sum(numbers, target):
    """
    在有序数组中找到两个数，它们的和等于 target
    返回它们的下标（1-indexed）
    """
    left, right = 0, len(numbers) - 1
    
    while left < right:
        s = numbers[left] + numbers[right]
        
        if s == target:
            return [left + 1, right + 1]  # 返回 1-indexed
        elif s < target:
            left += 1
        else:
            right -= 1
    
    return []

# 测试
print(two_sum([2, 7, 11, 15], 9))   # [1, 2]
print(two_sum([2, 3, 4], 6))       # [1, 3]
print(two_sum([-1, 0], -1))        # [1, 2]

示例：验证回文串

def is_palindrome(s: str) -> bool:
    """
    验证字符串是否是回文串（只考虑字母和数字，忽略大小写）
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        # 跳过非字母数字字符
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

# 测试
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))                       # False
print(is_palindrome(" "))                                # True

2. 快慢指针

快指针走得快，慢指针走得慢，常用于检测环形链表（也适用于数组）。

示例：移除元素

def remove_element(nums, val):
    """
    原地移除所有值为 val 的元素，返回新长度
    不需要考虑超出新长度后面的元素
    """
    slow = 0
    
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    
    return slow

# 测试
nums = [0, 1, 2, 2, 3, 0, 4, 2]
print(remove_element(nums, 2))  # 5
print(nums[:5])                  # [0, 1, 3, 0, 4]

示例：删除排序数组中的重复项

def remove_duplicates(nums):
    """
    删除排序数组中的重复项，每个元素最多出现两次
    """
    if len(nums) <= 2:
        return len(nums)
    
    slow = 2  # 从第三个位置开始
    
    for fast in range(2, len(nums)):
        if nums[fast] != nums[slow - 2]:
            nums[slow] = nums[fast]
            slow += 1
    
    return slow

# 测试
nums = [1, 1, 1, 2, 2, 3]
print(remove_duplicates(nums))  # 5
print(nums[:5])                  # [1, 1, 2, 2, 3]

3. 滑动窗口

滑动窗口是一种特殊的双指针，用于处理连续子数组/子串问题。

固定窗口大小

def fixed_window_sum(arr, k):
    """
    计算数组中每个长度为 k 的窗口的和
    """
    if len(arr) < k:
        return []
    
    window_sum = sum(arr[:k])
    result = [window_sum]
    
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        result.append(window_sum)
    
    return result

# 测试
print(fixed_window_sum([1, 2, 3, 4, 5], 3))  # [6, 9, 12]

示例：最大子数组和（变长窗口）

def max_subarray_len(k):
    """
    找到元素和等于 k 的最长子数组长度
    """
    max_len = 0
    prefix_sum = 0
    # 记录每个前缀和最早出现的位置
    seen = {0: -1}
    
    for i, num in enumerate(nums):
        prefix_sum += num
        
        # 检查是否存在 prefix_sum - k 的前缀
        if prefix_sum - k in seen:
            max_len = max(max_len, i - seen[prefix_sum - k])
        
        # 记录当前前缀和的最早位置
        if prefix_sum not in seen:
            seen[prefix_sum] = i
    
    return max_len

# 实际题目：最大子数组之和至少为 k
def max_subarray_len_k(nums, k):
    """
    找到长度最小的子数组，使得和 >= k
    返回最小长度，不存在则返回 0
    """
    left = 0
    min_len = float('inf')
    current_sum = 0
    
    for right in range(len(nums)):
        current_sum += nums[right]
        
        while current_sum >= k:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0

示例：无重复字符的最长子串

def length_of_longest_substring(s: str) -> int:
    """
    找到字符串中无重复字符的最长子串长度
    """
    char_index = {}  # 记录字符最近出现的位置
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        char = s[right]
        
        # 如果字符在窗口内出现过，移动左指针
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        
        char_index[char] = right
        max_len = max(max_len, right - left + 1)
    
    return max_len

# 测试
print(length_of_longest_substring("abcabcbb"))  # 3 ("abc")
print(length_of_longest_substring("bbbbb"))    # 1 ("b")
print(length_of_longest_substring("pwwkew"))   # 3 ("wke")

示例：和为 K 的子数组数量

def subarray_sum(nums, k):
    """
    统计和为 k 的连续子数组数量
    """
    count = 0
    prefix_sum = 0
    # 前缀和 -> 出现次数
    prefix_count = {0: 1}
    
    for num in nums:
        prefix_sum += num
        
        # 如果存在 prefix_sum - k 的前缀和，说明有解
        count += prefix_count.get(prefix_sum - k, 0)
        
        # 记录当前前缀和
        prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
    
    return count

# 测试
print(subarray_sum([1, 1, 1], 2))          # 2
print(subarray_sum([1, 2, 3], 3))          # 2 ([1,2], [3])

综合例题

示例：合并两个有序数组

def merge(nums1, m, nums2, n):
    """
    合并两个有序数组到 nums1
    从后往前填充，避免覆盖
    """
    p1 = m - 1      # nums1 的有效元素末尾
    p2 = n - 1      # nums2 末尾
    p = m + n - 1   # 合并后位置
    
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    
    # 如果 nums2 还有剩余，直接复制
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1

# 测试
nums1 = [1, 2, 3, 0, 0, 0]
merge(nums1, 3, [2, 5, 6], 3)
print(nums1)  # [1, 2, 2, 3, 5, 6]

示例：轮转数组

def rotate(nums, k):
    """
    将数组向右轮转 k 步
    使用三次反转：O(1) 空间
    """
    k %= len(nums)
    
    def reverse(l, r):
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1
    
    # 整体反转
    reverse(0, len(nums) - 1)
    # 前 k 个反转
    reverse(0, k - 1)
    # 后 n-k 个反转
    reverse(k, len(nums) - 1)

# 测试
nums = [-1, -100, 3, 99]
rotate(nums, 2)
print(nums)  # [3, 99, -1, -100]

常见题型总结

题型	技巧	典型问题
两数之和	对撞指针	有序数组两数之和
验证回文	对撞指针	回文串判断
移除元素	快慢指针	删除指定元素
子串问题	滑动窗口	无重复字符最长子串
子数组和	前缀和+哈希	和为 k 的子数组

[[返回算法首页|algorithm/index]]