数组与字符串 (Array & String)
数组与字符串 (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. 两数之和
使用哈希表优化查找:
目标和: 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
高级技巧
- 前缀和/差分数组优化区间操作
- 滑动窗口处理子串/子数组问题
- 双指针降低时间复杂度
- KMP算法处理字符串匹配
- Rabin-Karp算法处理字符串哈希
常见应用
-
数组:
- 排序算法实现
- 矩阵操作
- 区间处理
- 数据缓存
-
字符串:
- 文本处理
- 模式匹配
- 数据序列化
- URL处理