【JavaScript 算法】双指针法：高效处理数组问题

🔥 个人主页：空白诗

双指针法（Two Pointer Technique）是一种高效解决数组和字符串问题的算法技巧，通过维护两个指针来遍历数组，从而在特定条件下高效地解决问题。双指针法通常用于有序数组或字符串，常见的应用场景包括寻找和为特定值的两数、移除元素、合并两个有序数组等。本文将详细介绍双指针法的原理、实现及其应用。

---

一、算法原理

双指针法通过同时维护两个指针来遍历数组，从而在特定条件下高效地解决问题。双指针法的基本思想是：

1. 初始化两个指针，通常分别指向数组的起始位置和结束位置，或者都指向起始位置。
2. 根据特定的条件移动指针，直到满足问题的要求。

---

二、算法实现

示例问题1：两数之和 II - 输入有序数组

给定一个已按升序排列的数组，找到两个数使得它们的和等于目标数。

/*** 在有序数组中找到两个数使得它们的和等于目标数* @param {number[]} numbers - 输入的有序数组* @param {number} target - 目标和* @return {number[]} - 两个数的索引（从1开始计数）*/
function twoSum(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]; // 返回结果，索引从1开始计数} else if (sum < target) {left++; // 移动左指针} else {right--; // 移动右指针}}return []; // 如果没有找到符合条件的数，返回空数组
}// 示例
const numbers = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(numbers, target)); // 输出: [1, 2]

示例问题2：反转字符串中的元音字母

编写一个函数，以字符数组为输入，反转该字符串中的元音字母。

/*** 反转字符串中的元音字母* @param {string} s - 输入字符串* @return {string} - 反转元音字母后的字符串*/
function reverseVowels(s) {const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);const arr = s.split('');let left = 0;let right = arr.length - 1;while (left < right) {while (left < right && !vowels.has(arr[left])) {left++;}while (left < right && !vowels.has(arr[right])) {right--;}if (left < right) {[arr[left], arr[right]] = [arr[right], arr[left]];left++;right--;}}return arr.join('');
}// 示例
const s = "hello";
console.log(reverseVowels(s)); // 输出: "holle"

注释说明：

1. 两数之和 II - 输入有序数组：

   • let left = 0; let right = numbers.length - 1;：初始化两个指针，分别指向数组的起始位置和结束位置。
   • while (left < right)：遍历数组，直到两个指针相遇。
   • const sum = numbers[left] + numbers[right];：计算两个指针指向的数的和。
   • if (sum === target)：如果和等于目标数，返回两个数的索引。
   • else if (sum < target)：如果和小于目标数，移动左指针。
   • else：如果和大于目标数，移动右指针。

2. 反转字符串中的元音字母：

   • const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);：定义元音字母集合。
   • const arr = s.split('');：将字符串转换为字符数组。
   • let left = 0; let right = arr.length - 1;：初始化两个指针，分别指向数组的起始位置和结束位置。
   • while (left < right && !vowels.has(arr[left])) left++;：移动左指针，直到指向元音字母。
   • while (left < right && !vowels.has(arr[right])) right--;：移动右指针，直到指向元音字母。
   • if (left < right) [arr[left], arr[right]] = [arr[right], arr[left]]; left++; right--;：交换两个元音字母，并移动指针。

---

三、应用场景

1. 数组问题：如两数之和、三数之和、移除元素、合并两个有序数组等。
2. 字符串问题：如反转字符串中的元音字母、最长回文子串等。
3. 链表问题：如合并两个有序链表、删除链表中的节点等。

---

四、总结

双指针法是一种高效解决数组和字符串问题的算法技巧，通过同时维护两个指针来遍历数组，可以在特定条件下高效地解决问题。理解和掌握双指针法，可以有效解决许多实际问题，如两数之和、反转字符串中的元音字母等。

---