LeetCode | 解锁数组与字符串的秘密：经典题型详解与高效解法
1.理论
1. 1.核心概念
1.1.1.数组(Array)
定义：存储相同数据类型的元素的线性集合。
特点：支持随机访问（通过索引）;元素存储在连续内存中，支持高效的读写操作。
时间复杂度：访问：O(1);插入/删除：O(n)（平均情况下需要移动元素）
1.1.2.字符串(String)
定义：字符的序列，通常以数组的形式存储。
特点：通常是不可变（如 Python 的字符串类型）;涉及字符串操作时，额外空间的开销可能较大（如拼接操作）。
时间复杂度：访问字符：O(1);拼接：O(n)（取决于实现方式）
1.2. 常考算法技巧
1.2.1.双指针
用途：解决数组/字符串的遍历问题，尤其是涉及两个元素关系的题目。
常见场景：
- 对撞指针：从两端向中间逼近，解决回文检测、容器装水等问题。
- 快慢指针：用于环检测、删除重复元素等问题。
例题：盛最多水的容器,有效回文（Palindrome）
1.2.2.滑动窗口
用途：高效解决子数组或子串的相关问题。
常见场景：
- 固定窗口：滑动窗口大小固定。
- 动态窗口：窗口根据条件动态调整大小。
例题：最长无重复子串,最小覆盖子串
1.2.3.前缀和
用途：快速计算区间和。
常见场景：
- 求解固定区间的子数组和。
- 处理连续子数组满足某条件的题目。
例题：
和为 K 的子数组
1.2.4.排序与分组
用途：借助排序对数组进行归类、寻找规律。
常见场景：
对元素进行分组或分类（如字母异位词分组）。
最小或最大元素的快速计算。
例题：三数之和,合并区间
1.2.5.哈希表辅助
用途：提升查找效率。
常见场景：
记录元素出现次数。
查找特定关系的元素对。
例题：两数之和,多数元素
1.3. 高频题型分类
1.3.1.子数组与子串问题
典型题目：
最大子数组和（Kadane's Algorithm）
最长无重复子串
最小窗口子串
考察点：滑动窗口,动态规划
1.3.2.查找与排序问题
典型题目：两数之和,,三数之和,合并区间
考察点：排序后配合双指针,哈希表优化查找效率
1.3.3.数组变形问题
典型题目：螺旋矩阵,原地移除元素,旋转数组
考察点：模拟操作,空间优化
1.3.4.字符串匹配问题
典型题目：字符串相加,字符串反转,字符串排列
考察点：双指针操作,滑动窗口检测模式
2.真题
2.1.简单
【Leetcode 1】俩数之和 (Two Sum)
给定一个整数数组,返回两个数字的索引，使它们加起来等于 target.
示例 ：
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
def two_sum(nums,target):
num_map={} # 创建一个哈希表，用于存储数值和其对应的索引
for i ,num in enumerate(nums): # 遍历数组，i 和 num 分别表示数组中元素的索引和对应的值
complement=target-num # 计算需要的另一半数值
if complement in num_map: # 检查哈希表中是否有另一半数值
return [num_map[complement],i] # 如果存在，则返回其索引和当前索引
num_map[num]=i # 如果不存在，将当前数值和索引存入哈希表
#哈希表 num_map 动态存储遍历过的值和对应索引，并在每次迭代时检查是否已经满足条件。运行过程
| 索引 i | 当前值 num | 目标差值 complement=target−num | 哈希表状态 num_map | 返回值 |
|---|---|---|---|---|
| 0 | 2 | 7 | {2: 0} | - |
| 1 | 7 | 2 | {2: 0} | [0, 1] |
在索引 1 时，目标差值 2 已经存在于哈希表中，因此返回 [0,1]。
最优分析：
- 遍历一次数组：通过一次遍历和哈希表的辅助操作实现。
- 哈希表查找速度快：查找另一个值是否存在的时间复杂度为 O(1)。
- 无需额外排序：相比于双指针法（需要排序），此方法对数组原顺序无影响。