python-quick-start

Appearance

第2章 数组与字符串 ​

2.1 数组的内存连续性与随机访问 ​

数组是编程中最基础的数据结构之一，它的核心特点就是内存连续性。这意味着数组中的所有元素在内存中是挨着存储的，就像一排整齐的小房子。

这种连续性带来了随机访问的能力 - 我们可以通过索引直接跳到任意位置，时间复杂度是 O(1)。这就像你知道门牌号就能直接找到对应的房子，不用挨家挨户敲门。

数组基本操作方法表 ​

功能名称实例调用方法具体功能、注意事项、必需参数/可选参数
创建数组arr = [1, 2, 3]Python中使用列表实现数组，支持不同数据类型
访问元素arr[index]索引从0开始，负数索引从末尾开始，越界会抛出IndexError
修改元素arr[index] = value直接通过索引赋值，原地修改
获取长度len(arr)返回数组元素个数

让我们看一个完整的示例：

python
# 创建一个整数数组
numbers = [10, 20, 30, 40, 50]
print(f"原始数组: {numbers}")

# 随机访问 - 直接通过索引获取元素
try:
    # 访问第一个元素（索引0）
    first_element = numbers[0]
    print(f"第一个元素: {first_element}")
    
    # 访问最后一个元素（使用负索引）
    last_element = numbers[-1]
    print(f"最后一个元素: {last_element}")
    
    # 尝试越界访问（会抛出异常）
    invalid_element = numbers[10]
except IndexError as e:
    print(f"索引错误: {e}")

# 修改元素 - 原地修改
numbers[2] = 999
print(f"修改后数组: {numbers}")

# 获取数组长度
array_length = len(numbers)
print(f"数组长度: {array_length}")

# 遍历数组（展示内存连续性的优势）
print("遍历数组:")
for i in range(len(numbers)):
    print(f"索引 {i}: {numbers[i]}")

注意事项：

  • Python中的列表（list）虽然可以当作数组使用，但它实际上是动态数组，底层会自动扩容
  • 真正的静态数组在Python中可以通过array模块或numpy创建
  • 随机访问的时间复杂度是O(1)，但插入和删除操作（非末尾）的时间复杂度是O(n)

数组的内存连续性和随机访问特性使其成为许多算法的基础，特别是在需要频繁按索引访问元素的场景中表现优异。

2.2 双指针技巧：快慢指针、左右指针 ​

双指针技巧是解决数组和字符串问题的利器！它就像两个人在数组上跳舞，通过不同的移动策略来高效解决问题。

双指针主要分为两种类型：

  1. 快慢指针：两个指针以不同速度移动，常用于检测循环、找中点等
  2. 左右指针：两个指针从两端向中间移动，常用于排序数组的查找、反转等

双指针方法表 ​

功能名称实例调用方法具体功能、注意事项、必需参数/可选参数
快慢指针检测循环slow = fast = head; while fast and fast.next: slow=slow.next; fast=fast.next.next用于链表判环，快指针每次走两步，慢指针每次走一步
左右指针反转数组left=0; right=len(arr)-1; while left<right: swap(arr[left], arr[right]); left++; right--从两端向中间交换元素
两数之和（排序数组）while left < right: if arr[left] + arr[right] == target: return [left, right]利用排序性质，根据和的大小调整指针

先来看快慢指针的经典应用 - 检测数组中是否存在重复元素（模拟链表判环）：

python
def has_duplicate_in_array(nums):
    """
    使用快慢指针思想检测数组中是否有重复元素
    这里模拟的是Floyd判圈算法的思想
    """
    if not nums:
        return False
    
    # 将数组值作为下一个索引（假设数组值在有效范围内）
    def get_next_index(index):
        return nums[index]
    
    # 初始化快慢指针
    slow = fast = 0
    
    try:
        # 快慢指针移动
        while True:
            # 慢指针走一步
            slow = get_next_index(slow)
            # 快指针走两步
            fast = get_next_index(get_next_index(fast))
            
            # 如果相遇，说明有环（重复元素）
            if slow == fast:
                return True
                
    except IndexError:
        # 索引越界，说明没有环
        return False

# 测试快慢指针
test_array1 = [1, 2, 3, 4, 2]  # 有重复
test_array2 = [1, 2, 3, 4, 5]  # 无重复

print(f"数组 {test_array1} 是否有重复: {has_duplicate_in_array(test_array1)}")
print(f"数组 {test_array2} 是否有重复: {has_duplicate_in_array(test_array2)}")

再来看左右指针的应用 - 反转数组：

python
def reverse_array(arr):
    """
    使用左右指针反转数组
    """
    if not arr:
        return arr
    
    # 左右指针初始化
    left = 0
    right = len(arr) - 1
    
    # 当左指针小于右指针时继续交换
    while left < right:
        # 交换左右指针指向的元素
        arr[left], arr[right] = arr[right], arr[left]
        # 移动指针
        left += 1
        right -= 1
    
    return arr

# 测试左右指针反转
original_array = [1, 2, 3, 4, 5]
print(f"原始数组: {original_array}")

# 创建副本避免修改原数组
test_array = original_array.copy()
reversed_array = reverse_array(test_array)
print(f"反转后数组: {reversed_array}")

# 测试空数组和单元素数组
empty_array = []
single_array = [42]

print(f"空数组反转: {reverse_array(empty_array)}")
print(f"单元素数组反转: {reverse_array(single_array.copy())}")

注意事项：

  • 快慢指针通常用于链表问题，但在某些数组问题中也能巧妙应用
  • 左右指针要求能够从两端同时访问，适合处理对称性问题
  • 双指针技巧的关键是理解两个指针的移动逻辑和终止条件
  • 时间复杂度通常是O(n)，空间复杂度是O(1)，非常高效

双指针技巧的核心思想是通过两个指针的协作来避免嵌套循环，从而将时间复杂度从O(n²)优化到O(n)。

2.3 滑动窗口：固定长度与可变长度窗口 ​

滑动窗口就像一个可以移动的放大镜，让我们能够高效地处理子数组或子字符串问题。它特别适合解决"连续子序列"相关的问题。

滑动窗口分为两种：

  1. 固定长度窗口：窗口大小不变，只移动位置
  2. 可变长度窗口：窗口大小可以动态调整，通常用于找满足条件的最短/最长子序列

滑动窗口方法表 ​

功能名称实例调用方法具体功能、注意事项、必需参数/可选参数
固定窗口求和window_sum = sum(arr[:k]); for i in range(k, len(arr)): window_sum += arr[i] - arr[i-k]计算所有长度为k的子数组和，避免重复计算
可变窗口找最短子数组while right < len(arr): expand window; while condition_met: update result; shrink window找满足条件的最短连续子数组
字符串最小覆盖子串use hashmap to track char counts; expand right pointer; contract left when valid经典的可变窗口问题

先看固定长度窗口的例子 - 找最大平均子数组：

python
def find_max_average_subarray(nums, k):
    """
    找长度为k的连续子数组的最大平均值
    使用固定长度滑动窗口
    """
    if not nums or k <= 0 or k > len(nums):
        raise ValueError("无效的输入参数")
    
    # 计算第一个窗口的和
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    # 滑动窗口：移除左边元素，添加右边元素
    for i in range(k, len(nums)):
        # 移除窗口左边的元素
        window_sum -= nums[i - k]
        # 添加窗口右边的新元素
        window_sum += nums[i]
        # 更新最大和
        max_sum = max(max_sum, window_sum)
    
    # 返回最大平均值
    return max_sum / k

# 测试固定窗口
test_nums = [1, 12, -5, -6, 50, 3]
window_size = 4

try:
    max_avg = find_max_average_subarray(test_nums, window_size)
    print(f"数组: {test_nums}")
    print(f"窗口大小: {window_size}")
    print(f"最大平均值: {max_avg:.2f}")
except ValueError as e:
    print(f"错误: {e}")

# 边界测试
try:
    # 窗口大小等于数组长度
    single_window_avg = find_max_average_subarray([1, 2, 3], 3)
    print(f"整个数组平均值: {single_window_avg:.2f}")
except ValueError as e:
    print(f"错误: {e}")

再看可变长度窗口的例子 - 找最短子数组使得和大于等于目标值：

python
def min_subarray_len(target, nums):
    """
    找到和大于等于target的最短连续子数组长度
    使用可变长度滑动窗口
    """
    if not nums or target <= 0:
        return 0
    
    left = 0  # 窗口左边界
    current_sum = 0  # 当前窗口和
    min_length = float('inf')  # 最小长度，初始化为无穷大
    
    # 右指针遍历整个数组
    for right in range(len(nums)):
        # 扩展窗口：添加右边界元素
        current_sum += nums[right]
        
        # 当窗口满足条件时，尝试收缩左边界
        while current_sum >= target:
            # 更新最小长度
            min_length = min(min_length, right - left + 1)
            # 收缩窗口：移除左边界元素
            current_sum -= nums[left]
            left += 1
    
    # 如果没找到满足条件的子数组，返回0
    return min_length if min_length != float('inf') else 0

# 测试可变窗口
target_sum = 7
test_array = [2, 3, 1, 2, 4, 3]

min_len = min_subarray_len(target_sum, test_array)
print(f"数组: {test_array}")
print(f"目标和: {target_sum}")
print(f"最短子数组长度: {min_len}")

# 测试无解情况
no_solution = min_subarray_len(100, [1, 2, 3])
print(f"无解情况结果: {no_solution}")

注意事项：

  • 固定窗口的关键是维护窗口和，避免重复计算
  • 可变窗口通常使用"扩展-收缩"策略：先扩展右边界直到满足条件，再收缩左边界优化结果
  • 滑动窗口的时间复杂度是O(n)，因为每个元素最多被访问两次（一次加入，一次移除）
  • 要特别注意边界条件的处理，比如空数组、窗口大小为0等情况

滑动窗口技巧的核心在于理解什么时候扩展窗口，什么时候收缩窗口，以及如何维护窗口内的状态信息。

2.4 字符串不可变性与原地修改策略 ​

在Python中，字符串是不可变的（immutable），这意味着一旦创建就不能修改。这和其他语言（如C++）中的字符串很不一样。但是别担心，我们有很多聪明的方法来"模拟"字符串修改！

字符串不可变性的好处是线程安全和哈希缓存，但坏处是我们不能像数组那样直接修改字符。不过，我们可以使用一些策略来高效处理字符串问题。

字符串处理方法表 ​

功能名称实例调用方法具体功能、注意事项、必需参数/可选参数
字符串转列表修改char_list = list(s); char_list[i] = 'new_char'; result = ''.join(char_list)将字符串转为列表进行修改，再转回字符串
双指针原地反转s_list = list(s); left=0; right=len(s)-1; while left<right: swap; return ''.join(s_list)模拟原地修改，实际还是创建了新对象
字符串拼接优化result = ''.join([part1, part2, part3])避免使用+操作符多次拼接，提高效率
原地算法思想process string without extra space by using indices虽然不能真正原地修改，但可以模拟原地算法的思路

首先，让我们看看如何处理字符串反转问题：

python
def reverse_string_v1(s):
    """
    方法1：使用Python内置切片（最简单但可能不符合面试要求）
    """
    return s[::-1]

def reverse_string_v2(s):
    """
    方法2：转换为列表，双指针修改，再转回字符串
    这是最接近"原地修改"的方法
    """
    if not s:
        return s
    
    # 将字符串转换为字符列表（可变）
    char_list = list(s)
    
    # 双指针反转
    left = 0
    right = len(char_list) - 1
    
    while left < right:
        # 交换字符
        char_list[left], char_list[right] = char_list[right], char_list[left]
        left += 1
        right -= 1
    
    # 转回字符串
    return ''.join(char_list)

def reverse_words_in_string(s):
    """
    反转字符串中的单词顺序（但不反转单词内部字符）
    例如："hello world" -> "world hello"
    """
    if not s:
        return s
    
    # 分割单词，反转列表，重新连接
    words = s.split()
    reversed_words = words[::-1]
    return ' '.join(reversed_words)

# 测试字符串反转
test_string = "hello world"
print(f"原始字符串: '{test_string}'")

# 测试完整反转
reversed_v1 = reverse_string_v1(test_string)
reversed_v2 = reverse_string_v2(test_string)
print(f"完整反转 (v1): '{reversed_v1}'")
print(f"完整反转 (v2): '{reversed_v2}'")

# 测试单词顺序反转
words_reversed = reverse_words_in_string(test_string)
print(f"单词顺序反转: '{words_reversed}'")

# 测试边界情况
empty_string = ""
single_char = "a"
print(f"空字符串反转: '{reverse_string_v2(empty_string)}'")
print(f"单字符反转: '{reverse_string_v2(single_char)}'")

再来看一个更复杂的例子 - 原地移除字符串中的特定字符：

python
def remove_char_from_string(s, char_to_remove):
    """
    移除字符串中所有指定字符
    虽然不能真正原地修改，但使用双指针思想模拟原地算法
    """
    if not s:
        return s
    
    # 转换为字符列表
    char_list = list(s)
    
    # 双指针：write_index指向下一个要写入的位置
    write_index = 0
    
    # read_index遍历所有字符
    for read_index in range(len(char_list)):
        # 如果当前字符不是要移除的字符
        if char_list[read_index] != char_to_remove:
            # 写入到write_index位置
            char_list[write_index] = char_list[read_index]
            write_index += 1
    
    # 返回前write_index个字符组成的字符串
    return ''.join(char_list[:write_index])

def remove_duplicates_keep_order(s):
    """
    移除字符串中的重复字符，保持原有顺序
    使用集合记录已见过的字符
    """
    if not s:
        return s
    
    seen = set()
    result_chars = []
    
    for char in s:
        if char not in seen:
            seen.add(char)
            result_chars.append(char)
    
    return ''.join(result_chars)

# 测试字符移除
test_str = "hello world"
char_to_remove = 'l'

removed_result = remove_char_from_string(test_str, char_to_remove)
print(f"原始字符串: '{test_str}'")
print(f"移除字符 '{char_to_remove}': '{removed_result}'")

# 测试去重
duplicate_str = "programming"
unique_result = remove_duplicates_keep_order(duplicate_str)
print(f"去重前: '{duplicate_str}'")
print(f"去重后: '{unique_result}'")

# 测试特殊字符
special_str = "aabbcc"
removed_special = remove_char_from_string(special_str, 'b')
print(f"移除'b' from '{special_str}': '{removed_special}'")

注意事项：

  • Python字符串不可变是语言特性，无法绕过，但可以通过转换为列表来模拟修改
  • ''.join(list) 比多次字符串拼接更高效，因为字符串拼接会创建多个中间对象
  • 在算法面试中，即使语言不支持真正的原地修改，也要展示原地算法的思想
  • 对于大量字符串操作，考虑使用io.StringIO或bytearray来提高性能

虽然Python字符串不可变看起来是个限制，但通过巧妙的转换和算法思想，我们仍然能够高效解决各种字符串问题。关键是要理解背后的算法逻辑，而不是被语言特性束缚住手脚。