Day 9 - 双指针基础
📅 日期：2026年1月16日
🎯 主题：双指针基础 + 首尾指针与对撞指针
今日题目
题目1：两数之和 II - 输入有序数组 (Two Sum II - Input Array Is Sorted)
难度：⭐ 简单
链接：LeetCode 167. 两数之和 II - 输入有序数组
题目描述
给你一个下标从 1 开始的整数数组 numbers，该数组已按 非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2]，则 1 <= index1 < index2 <= numbers.length。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案，而且你 不可以 重复使用相同的元素。
示例：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。提示：
2 <= numbers.length <= 3 * 10^4-1000 <= numbers[i] <= 1000numbers按 非递减顺序 排列-1000 <= target <= 1000- 仅存在一个有效答案
解题思路
方法一：双指针（对撞指针） ✅ 推荐
核心思想：
- 利用数组有序，使用首尾双指针：
left指向最小元素，right指向最大元素 - 计算
sum = numbers[left] + numbers[right] - 若
sum == target，返回[left + 1, right + 1]（题目下标从 1 开始） - 若
sum < target，说明和小了，left右移（选更大数） - 若
sum > target，说明和大了，right左移（选更小数） - 直到两指针相遇
关键点：
- 有序数组才能用对撞指针缩小范围
- 时间复杂度：O(n)；空间复杂度：O(1)
方法二：二分查找
固定一个数，对另一个数在剩余区间内二分查找 target - numbers[i]。时间复杂度 O(n log n)。
代码实现
方法一：双指针（对撞指针）
java
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
// 题目下标从 1 开始
return new int[]{left + 1, right + 1};
}
if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{-1, -1};
}
}复杂度分析
- 时间复杂度：O(n)，最多遍历数组一次
- 空间复杂度：O(1)，仅使用常数额外空间
题目2：验证回文串 (Valid Palindrome)
难度：⭐ 简单
题目描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串。
字母和数字都属于 字母数字字符。
给你一个字符串 s，如果它是 回文串，返回 true；否则，返回 false。
示例：
输入：s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。
输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。
输入：s = " "
输出：true
解释：在移除非字母数字字符后，s 为空字符串 "" 。空字符串是回文串。提示：
1 <= s.length <= 2 * 10^5s仅由可打印的 ASCII 字符组成
解题思路
方法一：双指针（首尾向中间） ✅ 推荐
核心思想：
- 使用
left从首、right从尾向中间移动 - 若当前字符不是字母或数字，则跳过（
left++或right--） - 若都是字母数字，则比较小写是否相等；不等则返回
false - 相等则
left++、right--继续 - 当
left >= right时结束，返回true
关键点：
- 统一转小写再比较：
Character.toLowerCase(c) - 判断字母数字：
Character.isLetterOrDigit(c) - 时间复杂度：O(n)；空间复杂度：O(1)
方法二：过滤 + 反转
先过滤出仅字母数字的字符串并转小写，再与反转后的字符串比较。需要 O(n) 额外空间。
代码实现
方法一：双指针
java
class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.length() == 0) {
return true;
}
int left = 0;
int right = s.length() - 1;
while (left < right) {
// 跳过非字母数字字符
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
// 比较（转小写）
char c1 = Character.toLowerCase(s.charAt(left));
char c2 = Character.toLowerCase(s.charAt(right));
if (c1 != c2) {
return false;
}
left++;
right--;
}
return true;
}
}方法二：过滤 + 反转
java
class Solution {
public boolean isPalindrome(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isLetterOrDigit(c)) {
sb.append(Character.toLowerCase(c));
}
}
String filtered = sb.toString();
String reversed = sb.reverse().toString();
return filtered.equals(reversed);
}
}复杂度分析
- 时间复杂度：O(n)，遍历字符串
- 空间复杂度：
- 双指针：O(1)
- 过滤+反转：O(n)
今日总结
学到了什么？
- 对撞指针：有序数组上首尾指针根据和与 target 的关系向中间收缩
- 首尾比较：回文、对称类问题用首尾指针向中间移动并比较
- 跳过无关字符：在循环内用 while 跳过非字母数字，再比较
- 下标转换：题目要求下标从 1 开始时，返回
left + 1, right + 1
关键技巧
| 技巧 | 适用场景 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 对撞指针 | 有序数组、两数之和 | O(n) | O(1) |
| 首尾指针 | 回文、对称、反转 | O(n) | O(1) |
| 跳过条件 | 只处理部分字符 | O(n) | O(1) |
双指针要点
对撞指针：
- 条件：数组有序（或可排序）
- 左小右大时：和小则左移、和大则右移
- 典型题：两数之和 II、盛最多水的容器、三数之和
首尾指针：
- 从两端向中间移动，每次比较或交换
- 典型题：验证回文串、反转字符串
常见错误：
- 忘记题目下标从 1 开始
- 回文判断时未统一大小写或未跳过非字母数字
- 移动指针时越界（先判
left < right再取字符）
相似题目推荐
明日计划
- Day 10 双指针进阶
- 练习：盛最多水的容器、接雨水等