JS双指针|极客笔记

JS双指针

双指针是一种常见的算法技巧，它经常用于解决数组或者链表相关的问题。在JavaScript中，双指针技巧可以帮助我们高效地解决一些问题，比如查找数组中的两个数使它们的和等于一个给定的值、判断一个字符串是否为回文等。

在本文中，我们将详细介绍JS中双指针的原理、应用场景和实际代码示例。

原理

双指针技术通常指的是在数组或者链表中使用两个指针，它们可以是快慢指针、左右指针等。双指针可以根据具体问题灵活选择指针的移动方式，从而快速地解决问题。

在解决数组问题时，我们通常使用快慢指针，一个指针快速移动，一个指针慢速移动，根据具体问题场景，我们可以调整快慢指针的移动方式，比如两指针之间的距离、两指针的移动方向等。

在解决链表问题时，我们通常使用左右指针，一个指针从左向右移动，一个指针从右向左移动，根据具体问题场景，我们同样可以调整左右指针的移动方式，比如两指针之间的距离、两指针的移动方向等。

应用场景

双指针技巧在解决一些数组、链表相关问题时非常有效，比如：

判断一个字符串是否为回文
求解两数之和
找到两个链表的交点
寻找数组中的两个数，它们的和为给定值

实际代码示例

判断一个字符串是否为回文

const isPalindrome = (str) => {
  let left = 0;
  let right = str.length - 1;

  while (left < right) {
    if (str[left] !== str[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
};

// 测试用例
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello")); // false

求解两数之和

const twoSum = (nums, target) => {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return [];
};

// 测试用例
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6)); // [1, 2]

找到两个链表的交点

const getIntersectionNode = (headA, headB) => {
  let pA = headA;
  let pB = headB;

  while (pA !== pB) {
    pA = pA ? pA.next : headB;
    pB = pB ? pB.next : headA;
  }

  return pA;
};

// 测试用例
// 构造链表：listA -> 4 -> 1 -> 8 -> 4
//            listB -> 5 -> 0 -> 1 -> 8 -> 4
// 交点为节点值为8的节点
const listA = { val: 4, next: { val: 1, next: { val: 8, next: { val: 4, next: null } } } };
const listB = { val: 5, next: { val: 0, next: { val: 1, next: { val: 8, next: { val: 4, next: null } } } } };
console.log(getIntersectionNode(listA, listB)); // { val: 8, next: { val: 4, next: null } }

寻找数组中的两个数，它们的和为给定值

const twoSumArr = (nums, target) => {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) {
      return [nums[left], nums[right]];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return [];
};

// 测试用例
console.log(twoSumArr([2, 7, 11, 15], 9)); // [2, 7]