对撞指针
# 对撞指针
对撞指针是双指针中的一种常见类型，一个指针从头部开始，而另一个指针从尾部开始。典型的应用场景是从两端向中间迭代数组。一般来说，利用对撞指针的前提是数组有序。经典题型有：反转字符串、验证回文串、两数之和等。
# 对撞指针图示
# 经典题型
话不多说，直接上经典题型，因为也没太多好说的。
# LC 344. 反转字符串 (opens new window)
Q：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
A：典型的对撞指针解法。
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function (s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
const tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
};
# LC 125. 验证回文串 (opens new window)
Q：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
A：双指针，对撞指针
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function (s) {
const isValid = (char) => {
const isNumber = char >= "0" && char <= "9";
const isLetter = (char >= "A" && char <= "Z") || (char >= "a" && char <= "z");
return isNumber || isLetter;
}
let left = 0;
let right = s.length - 1;
while (left < right) {
if (!isValid(s[left])) {
left++;
} else if (!isValid(s[right])) {
right--;
} else {
if (s[left].toLowerCase() != s[right].toLowerCase()) return false;
left++;
right--;
}
}
return true;
};
# LC 167.两数之和-ii-输入有序数组 (opens new window)
Q：给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
A：由于数组已有序，可用双指针，对撞指针解决。
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum == target) return [left + 1, right + 1];
if (sum < target) {
left++;
} else {
right--;
}
}
return [];
};
# LC 11. 盛最多水的容器 (opens new window)
Q：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
A：对撞指针的经典题目，需要仔细理解，详细题解看官方题解
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
let left = 0;
let right = height.length - 1;
let ans = 0;
while (left < right) {
// 计算当前面积
const area = (right - left) * Math.min(height[left], height[right]);
ans = Math.max(ans, area);
// 移动较小的一侧
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return ans;
};