1. 两指针技巧介绍
两指针技巧是一种常见的解决问题的算法，它通常用来寻找一个区间内的数据，或者比较两个有序数组的数据。这种算法的核心思想是通过控制两个指针来遍历数据，从而达到寻找或比较数据的目的。在JavaScript中，两指针技巧可以很好地解决一些数组和字符串相关的问题，下面就让我们来看一些使用两指针技巧的JavaScript程序。
2. 使用两指针寻找有序数组中的相同元素
2.1 问题描述
给定两个有序数组arr1和arr2，请找出它们中相同的元素，输出这些元素。例如：
const arr1 = [1, 3, 4, 6, 7, 9];
const arr2 = [1, 2, 4, 5, 9, 10];
// 输出：[1, 4, 9]
2.2 解决方案
由于两个数组都是有序的，我们可以分别使用两个指针p1和p2指向数组的开头，然后比较它们所指向的元素的大小。如果这两个元素相等，则说明它们是相同的元素，我们将它加入到结果数组res中，同时移动指针p1和p2以继续寻找相同的元素。如果arr1[p1]小于arr2[p2]，则将指针p1向后移动；反之，将指针p2向后移动。直到指针p1或p2超出数组的长度，我们就得到了所有相同的元素。
下面是使用两指针技巧寻找有序数组中相同元素的代码实现：
function findSameElements(arr1, arr2) {
let p1 = 0, p2 = 0;
const res = [];
while (p1 < arr1.length && p2 < arr2.length) {
if (arr1[p1] === arr2[p2]) {
res.push(arr1[p1]);
p1++;
p2++;
} else if (arr1[p1] < arr2[p2]) {
p1++;
} else {
p2++;
}
}
return res;
}
const arr1 = [1, 3, 4, 6, 7, 9];
const arr2 = [1, 2, 4, 5, 9, 10];
console.log(findSameElements(arr1, arr2)); // [1, 4, 9]
在上面的代码中，我们首先初始化两个指针p1和p2，以及一个结果数组res，然后进行指针的循环比较，直到结束。最后，我们返回包含所有相同元素的结果数组res。
3. 使用两指针寻找最长回文子串
3.1 问题描述
给定一个字符串s，请找出其中的最长回文子串（回文字符串是指正着和倒着读都相同的字符串）。例如：
const s = "babad";
// 输出："bab"或"aba"
3.2 解决方案
我们可以使用两指针技巧来寻找最长回文子串。具体来说，我们可以在字符串中以每个字符为中心，向左右两端扩展指针来判断是否是回文字符串。因为回文字符串的长度是奇数或偶数，所以我们需要考虑以每个字符为中心的偶数长度和奇数长度的回文字符串。对于一个长度为n的字符串，我们需要进行n次以每个字符为中心的扩展操作，每次操作的时间复杂度为O(n)，所以总的时间复杂度为O(n^2)。
下面是使用两指针技巧寻找最长回文子串的代码实现：
function longestPalindrome(s) {
let maxLen = 0, start = 0;
for (let i = 0; i < s.length; i++) {
let len1 = expandAroundCenter(s, i, i); // 以i为中心扩展奇数长度的回文字符串
let len2 = expandAroundCenter(s, i, i + 1); // 以i和i+1为中心扩展偶数长度的回文字符串
let len = Math.max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - Math.floor((maxLen - 1) / 2);
}
}
return s.substr(start, maxLen);
}
function expandAroundCenter(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
}
const s = "babad";
console.log(longestPalindrome(s)); // "bab"
在上面的代码中，我们首先遍历字符串s中的每个字符i，然后以i为中心，调用expandAroundCenter()函数进行回文字符串的扩展。具体来说，expandAroundCenter()函数分别从left和right两端开始向左右两端扩展，如果s[left] === s[right]，则继续扩展，否则停止扩展。最后，返回回文字符串的长度。
在longestPalindrome()函数中，我们分别调用expandAroundCenter()函数求得对于以i为中心的奇数长度的回文字符串和偶数长度的回文字符串的长度，然后取它们之中的最大值len。如果len大于当前记录的最大长度maxLen，则更新记录的最大长度maxLen和起点start，最后返回这个最长回文子串。
4. 总结
本文介绍了两指针技巧在JavaScript中的应用，我们分别使用两指针技巧解决了两个问题：寻找有序数组中的相同元素和寻找最长回文子串。这两个问题都是很经典的算法问题，使用两指针技巧可以很好地解决它们。在实际应用中，我们还可以使用两指针技巧来解决一些其他的数组和字符串相关的问题，例如寻找数组的中位数、实现滑动窗口算法等等。通过掌握两指针技巧，我们可以更好地理解和掌握算法，从而在实际开发中更好地解决问题。