skillhub-117-code-mentor/references/data-structures/arrays-strings.md

数组与字符串参考

数组

核心概念

数组（array） 是存储在连续内存位置上的元素集合。数组提供 O(1) 的随机访问，但插入/删除操作（末尾除外）为 O(n)。

关键属性：

• 固定或动态大小（取决于语言）
• 同质元素（相同类型）
• 多数语言中从零开始索引
• 连续内存分配

常见操作

操作	时间复杂度	说明
访问	O(1)	直接索引查找
搜索	O(n)	若已排序则 O(log n) + 二分查找
插入（末尾）	O(1) 均摊	可能触发扩容
插入（任意位置）	O(n)	移动元素
删除（末尾）	O(1)	Pop 操作
删除（任意位置）	O(n)	移动元素

Python 实现

# Array/List operations
arr = [1, 2, 3, 4, 5]

# Access
element = arr[2]  # O(1)

# Search
index = arr.index(3)  # O(n)
exists = 3 in arr  # O(n)

# Insert
arr.append(6)  # O(1) at end
arr.insert(2, 10)  # O(n) at arbitrary position

# Delete
arr.pop()  # O(1) from end
arr.pop(2)  # O(n) from arbitrary position
arr.remove(10)  # O(n) - finds and removes

# Slicing
subarray = arr[1:4]  # O(k) where k is slice size

# Common patterns
reversed_arr = arr[::-1]
sorted_arr = sorted(arr)  # O(n log n)

JavaScript 实现

// Array operations
const arr = [1, 2, 3, 4, 5];

// Access
const element = arr[2];  // O(1)

// Search
const index = arr.indexOf(3);  // O(n)
const exists = arr.includes(3);  // O(n)

// Insert
arr.push(6);  // O(1) at end
arr.splice(2, 0, 10);  // O(n) at arbitrary position

// Delete
arr.pop();  // O(1) from end
arr.splice(2, 1);  // O(n) from arbitrary position

// Slicing
const subarray = arr.slice(1, 4);  // O(k)

// Common patterns
const reversedArr = arr.reverse();
const sortedArr = arr.sort((a, b) => a - b);  // O(n log n)

---

字符串

核心概念

字符串（string） 是字符序列。在大多数语言中，字符串是不可变的（Python、Java），或被视为字符数组（C++，JavaScript 在某些情况下允许修改）。

关键属性：

• 在 Python、Java、JavaScript（基本类型）中不可变
• 在 C++ 中是字符数组
• 需考虑 UTF-8/UTF-16 编码
• 拼接操作可能代价高昂

常见操作

操作	时间复杂度	说明
访问	O(1)	直接索引查找
拼接	O(n + m)	若不可变则创建新字符串
子串	O(k)	k = 子串长度
搜索	O(n * m)	朴素算法；使用 KMP 为 O(n + m)
替换	O(n)	不可变语言中创建新字符串

Python 实现

s = "hello world"

# Access
char = s[0]  # O(1)

# Slicing
substring = s[0:5]  # O(k)
substring = s[::-1]  # Reverse O(n)

# Search
index = s.find("world")  # O(n), returns -1 if not found
index = s.index("world")  # O(n), raises error if not found
exists = "world" in s  # O(n)

# Modification (creates new string)
s_upper = s.upper()
s_lower = s.lower()
s_replaced = s.replace("world", "python")

# Split and join
words = s.split()  # O(n)
joined = " ".join(words)  # O(n)

# Common patterns
is_alpha = s.isalpha()
is_digit = s.isdigit()
stripped = s.strip()  # Remove whitespace

JavaScript 实现

let s = "hello world";

// Access
const char = s[0];  // O(1)

// Slicing
const substring = s.slice(0, 5);  // O(k)
const reversed = s.split('').reverse().join('');  // O(n)

// Search
const index = s.indexOf("world");  // O(n), returns -1 if not found
const exists = s.includes("world");  // O(n)

// Modification (creates new string)
const sUpper = s.toUpperCase();
const sLower = s.toLowerCase();
const sReplaced = s.replace("world", "javascript");

// Split and join
const words = s.split(' ');  // O(n)
const joined = words.join(' ');  // O(n)

// Common methods
const trimmed = s.trim();
const startsWithHello = s.startsWith("hello");
const endsWithWorld = s.endsWith("world");

---

常见数组/字符串模式

1. 双指针

问题：检查字符串是否为回文

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. 滑动窗口

问题：大小为 k 的最大子数组和

def max_sum_subarray(arr, k):
    if len(arr) < k:
        return None

    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)

    return max_sum

3. 前缀和

问题：区间和查询

class RangeSumQuery:
    def __init__(self, nums):
        self.prefix = [0]
        for num in nums:
            self.prefix.append(self.prefix[-1] + num)

    def sum_range(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

4. 哈希表统计频率

问题：字符串中第一个不重复的字符

def first_unique_char(s):
    from collections import Counter

    freq = Counter(s)

    for i, char in enumerate(s):
        if freq[char] == 1:
            return i

    return -1

5. 字符串构建器（性能优化）

问题：高效字符串拼接

# BAD: O(n²) due to immutability
result = ""
for i in range(n):
    result += str(i)  # Creates new string each time

# GOOD: O(n) using list
result = []
for i in range(n):
    result.append(str(i))
final_result = "".join(result)

---

进阶技巧

1. Kadane 算法（最大子数组和）

def max_subarray_sum(nums):
    """Find maximum sum of contiguous subarray."""
    max_current = max_global = nums[0]

    for i in range(1, len(nums)):
        max_current = max(nums[i], max_current + nums[i])
        max_global = max(max_global, max_current)

    return max_global

时间复杂度：O(n)，空间复杂度：O(1)

2. KMP 字符串匹配

def kmp_search(text, pattern):
    """Knuth-Morris-Pratt string matching."""
    def compute_lps(pattern):
        lps = [0] * len(pattern)
        length = 0
        i = 1

        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1

        return lps

    lps = compute_lps(pattern)
    i = j = 0

    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == len(pattern):
            return i - j  # Pattern found
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return -1  # Not found

时间复杂度：O(n + m)，空间复杂度：O(m)

3. Rabin-Karp（滚动哈希）

def rabin_karp(text, pattern):
    """Rolling hash string matching."""
    d = 256  # Number of characters
    q = 101  # Prime number
    m = len(pattern)
    n = len(text)
    p = 0  # Hash value for pattern
    t = 0  # Hash value for text
    h = 1

    # Calculate h = pow(d, m-1) % q
    for i in range(m - 1):
        h = (h * d) % q

    # Calculate initial hash values
    for i in range(m):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q

    # Slide pattern over text
    for i in range(n - m + 1):
        if p == t:
            # Check characters one by one
            if text[i:i + m] == pattern:
                return i

        # Calculate hash for next window
        if i < n - m:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q
            if t < 0:
                t += q

    return -1

平均时间复杂度：O(n + m)，最坏情况：O(n * m)

---

常见陷阱与最佳实践

陷阱 1：差一错误

# WRONG
for i in range(len(arr) - 1):  # Misses last element
    print(arr[i])

# CORRECT
for i in range(len(arr)):
    print(arr[i])

陷阱 2：遍历时修改

# WRONG
for item in arr:
    if item % 2 == 0:
        arr.remove(item)  # Can skip elements

# CORRECT
arr = [item for item in arr if item % 2 != 0]
# Or iterate backwards
for i in range(len(arr) - 1, -1, -1):
    if arr[i] % 2 == 0:
        arr.pop(i)

陷阱 3：循环中拼接字符串

# INEFFICIENT: O(n²)
result = ""
for i in range(n):
    result += str(i)

# EFFICIENT: O(n)
result = "".join(str(i) for i in range(n))

最佳实践 1：使用内置函数

# Manual max finding
max_val = arr[0]
for val in arr:
    if val > max_val:
        max_val = val

# Better
max_val = max(arr)

最佳实践 2：列表推导式

# Traditional loop
squares = []
for x in range(10):
    squares.append(x ** 2)

# List comprehension (more Pythonic)
squares = [x ** 2 for x in range(10)]

最佳实践 3：使用 Enumerate 获取索引与值

# Manual indexing
for i in range(len(arr)):
    print(f"Index {i}: {arr[i]}")

# Better
for i, val in enumerate(arr):
    print(f"Index {i}: {val}")

---

面试问题检查清单

在解决数组/字符串问题时：

1. 明确约束条件：

   • 数组大小限制？
   • 数组能否为空？
   • 取值范围？
   • 是否允许原地修改？

2. 考虑边界情况：

   • 空数组/空字符串
   • 单个元素
   • 所有元素相同
   • 已排序
   • 负数（针对数组）

3. 选择方法：

   • 先暴力求解（验证逻辑）
   • 优化（双指针、哈希表、滑动窗口）
   • 考虑时间/空间权衡

4. 用示例测试：

   • 常规情况
   • 边界情况
   • 大量输入

5. 分析复杂度：

   • 时间复杂度
   • 空间复杂度
   • 能否进一步优化？