数组与字符串
数组和字符串是最基础的数据结构，在算法面试中出现频率极高。掌握数组和字符串的处理技巧，特别是双指针和滑动窗口算法，对于通过 Microsoft SDE 面试至关重要。
数组基础
数组的特点
- 连续内存：元素在内存中连续存储
- 随机访问：可以通过索引 O(1) 时间访问任意元素
- 固定大小：大多数语言中数组大小固定（动态数组除外）
数组的基本操作
# 创建数组
arr = [1, 2, 3, 4, 5]
# 访问元素：O(1)
first = arr[0]
# 修改元素：O(1)
arr[0] = 10
# 遍历数组：O(n)
for num in arr:
print(num)
# 查找元素：O(n)
target = 3
if target in arr:
index = arr.index(target)
字符串基础
字符串的特点
- 不可变：大多数语言中字符串是不可变的
- 字符数组：可以看作字符的数组
- 常用操作：拼接、分割、查找、替换
字符串的基本操作
# 创建字符串
s = "Hello World"
# 访问字符：O(1)
first_char = s[0]
# 字符串拼接：O(n)
new_s = s + "!"
# 字符串查找：O(n)
index = s.find("World")
# 字符串分割：O(n)
words = s.split(" ")
# 字符串替换：O(n)
new_s = s.replace("World", "Python")
双指针技巧
双指针是处理数组和字符串问题的常用技巧，可以显著降低时间复杂度。
1. 左右指针
应用场景：有序数组、回文串判断
# 两数之和（有序数组）
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return []
# 回文串判断
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
2. 快慢指针
应用场景：链表环检测、数组去重、找中点
# 删除有序数组中的重复项
def remove_duplicates(nums):
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# 找链表中点（伪代码）
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
3. 滑动窗口
应用场景：子串、子数组问题
# 最长无重复字符子串
def length_of_longest_substring(s):
char_map = {}
left = 0
max_len = 0
for right in range(len(s)):
if s[right] in char_map:
left = max(left, char_map[s[right]] + 1)
char_map[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len
# 最小覆盖子串
def min_window(s, t):
need = {}
for char in t:
need[char] = need.get(char, 0) + 1
window = {}
left = right = 0
valid = 0
start = 0
min_len = float('inf')
while right < len(s):
c = s[right]
right += 1
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
while valid == len(need):
if right - left < min_len:
start = left
min_len = right - left
d = s[left]
left += 1
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
return "" if min_len == float('inf') else s[start:start + min_len]
常见题目类型
1. 数组操作
题目：移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
def move_zeros(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
2. 字符串匹配
题目：实现 strStr()
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置（从 0 开始）。
def str_str(haystack, needle):
if not needle:
return 0
if len(needle) > len(haystack):
return -1
for i in range(len(haystack) - len(needle) + 1):
if haystack[i:i + len(needle)] == needle:
return i
return -1
3. 回文串问题
题目：最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。
def longest_palindrome(s):
def expand_around_center(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]
longest = ""
for i in range(len(s)):
# 奇数长度
palindrome1 = expand_around_center(i, i)
# 偶数长度
palindrome2 = expand_around_center(i, i + 1)
longest = max(longest, palindrome1, palindrome2, key=len)
return longest
面试技巧
1. 边界情况处理
- 空数组/空字符串
- 单个元素
- 所有元素相同
- 数组越界
2. 空间优化
- 尽量使用原地操作（in-place）
- 使用双指针减少额外空间
- 考虑是否可以重用输入数组
3. 时间优化
- 使用哈希表优化查找
- 使用双指针减少嵌套循环
- 使用滑动窗口处理子串问题
总结
数组和字符串是算法面试的基础：
- 掌握基本操作：熟悉数组和字符串的常用操作
- 双指针技巧：左右指针、快慢指针的应用
- 滑动窗口：处理子串、子数组问题的有效方法
- 常见题型：数组操作、字符串匹配、回文串问题
通过大量练习，你将能够快速识别问题类型并选择合适的方法。
接下来，让我们学习链表，这是另一种重要的线性数据结构。