数组与字符串 (Array & String)

LeetCodeArrayString数组字符串数据结构

数组与字符串 (Array & String)

数组和字符串是最基础的数据结构，是其他复杂数据结构的基石。

基础概念

数组

静态数组:
[1] [2] [3] [4] [5]
 0   1   2   3   4  (索引)

动态数组:
[1] [2] [3] [ ] [ ]  (容量5，实际大小3)

基本操作:

  • 访问: O(1)
  • 搜索: O(n)
  • 插入: O(n)
  • 删除: O(n)
  • 追加: 平均O(1)

特点:

  • 连续内存空间
  • 随机访问
  • 固定大小（静态）或可扩容（动态）
  • 支持切片操作

字符串

字符串示例:
"Hello"  =>  ['H'] ['e'] ['l'] ['l'] ['o']
              0    1    2    3    4   (索引)

基本操作:

  • 连接: str1 + str2
  • 切片: str[i:j]
  • 查找: str.find()
  • 替换: str.replace()

特点:

  • 不可变（Python, Java）
  • 支持Unicode
  • 常用于文本处理
  • 有丰富的内置方法

常见技巧

1. 双指针技术

示例: 反转数组
[1] [2] [3] [4] [5]
 ↑               ↑
left           right

[5] [2] [3] [4] [1]
    ↑       ↑
   left   right

[5] [4] [3] [2] [1]
       ↑   ↑
     left right

2. 滑动窗口

固定窗口大小为3:
[1] [2] [3] [4] [5]
 ←---→
  [2] [3] [4] [5]
  ←---→
   [3] [4] [5]
   ←---→

3. 前缀和

原数组:     [3] [1] [2] [4] [5]
前缀和数组: [3] [4] [6] [10][15]

经典问题

1. 两数之和

LeetCode 1 - Two Sum

使用哈希表优化查找:

目标和: 9
数组: [2, 7, 11, 15]

步骤1: {2: 0}           寻找 9-2=7
步骤2: {2: 0, 7: 1}     找到 7，返回 [0,1]
def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

2. 最长连续序列

LeetCode 128 - Longest Consecutive Sequence

使用集合查找连续序列:

输入: [100, 4, 200, 1, 3, 2]

转换为集合: {1, 2, 3, 4, 100, 200}

查找序列:
1 -> 2 -> 3 -> 4     (长度4)
100                   (长度1)
200                   (长度1)

返回: 4
def longestConsecutive(nums):
    num_set = set(nums)
    max_length = 0
    
    for num in num_set:
        if num - 1 not in num_set:  # 序列的起点
            current = num
            current_length = 1
            
            while current + 1 in num_set:
                current += 1
                current_length += 1
                
            max_length = max(max_length, current_length)
    
    return max_length

3. 字符串相乘

LeetCode 43 - Multiply Strings

模拟手算乘法过程:

    1 2 3
  × 4 5 6
---------
    7 3 8  (123 × 6)
  6 1 5 0  (123 × 50)
4 9 2 0 0  (123 × 400)
---------
5 6 0 8 8
def multiply(num1, num2):
    if num1 == "0" or num2 == "0":
        return "0"
        
    # 将字符串转换为数组，便于处理
    n1 = [int(i) for i in num1]
    n2 = [int(i) for i in num2]
    
    # 结果最多为两个数字长度之和
    result = [0] * (len(n1) + len(n2))
    
    # 从右往左遍历
    for i in range(len(n1)-1, -1, -1):
        for j in range(len(n2)-1, -1, -1):
            product = n1[i] * n2[j]
            p1, p2 = i + j, i + j + 1
            total = product + result[p2]
            
            result[p2] = total % 10
            result[p1] += total // 10
            
    # 去除前导零
    while len(result) > 1 and result[0] == 0:
        result.pop(0)
        
    return ''.join(map(str, result))

4. 最长回文子串

LeetCode 5 - Longest Palindromic Substring

中心扩展法:

输入: "babad"

以每个字符为中心扩展:
b       => b
a       => a
b(aba)  => aba
a       => a
d       => d

以字符间隙为中心扩展:
b|a     => 无
a|b     => 无
b|a     => 无
a|d     => 无

最长回文子串: "aba"
def longestPalindrome(s):
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    result = ""
    for i in range(len(s)):
        # 奇数长度回文
        odd = expand(i, i)
        if len(odd) > len(result):
            result = odd
            
        # 偶数长度回文
        even = expand(i, i + 1)
        if len(even) > len(result):
            result = even
            
    return result

高级技巧

  1. 前缀和/差分数组优化区间操作
  2. 滑动窗口处理子串/子数组问题
  3. 双指针降低时间复杂度
  4. KMP算法处理字符串匹配
  5. Rabin-Karp算法处理字符串哈希

常见应用

  • 数组：

    • 排序算法实现
    • 矩阵操作
    • 区间处理
    • 数据缓存

  • 字符串：

    • 文本处理
    • 模式匹配
    • 数据序列化
    • URL处理

相关题目