Javascript 两指针技巧的JavaScript程序

在本文中，我们将介绍Javascript中的两指针技巧，并提供一些示例代码来展示其用法和实际应用。

1. 双指针技巧简介

双指针技巧是一种在数组和字符串相关问题中经常使用的算法。通过使用两个指针，我们可以在不使用额外空间的情况下解决一些复杂的问题。双指针技巧通常用于处理有序数组或链表，但也可以应用于其他数据结构。

2. 快慢指针

快慢指针是双指针技巧中最常见的一种。它通常用于解决链表相关问题，如判断链表中是否存在环、找到链表的中间节点等。

以下是一个使用快慢指针判断链表中是否存在环的示例代码：

class ListNode {
  constructor(value) {
    this.val = value;
    this.next = null;
  }
}

function hasCycle(head) {
  if (head === null || head.next === null) {
    return false;
  }

  let slow = head;
  let fast = head.next;

  while (slow !== fast) {
    if (fast === null || fast.next === null) {
      return false;
    }
    slow = slow.next;
    fast = fast.next.next;
  }

  return true;
}

在上面的代码中，我们使用了快慢两个指针，分别命名为slow和fast。快指针每次移动两步，慢指针每次移动一步，如果链表中存在环，那么快指针早晚会追上慢指针。

3. 左右指针

左右指针也是双指针技巧中常用的一种。它通常用于解决数组中的问题，如在有序数组中查找目标元素、判断数组中是否存在三个数的和等于目标值等。

以下是一个使用左右指针在有序数组中查找目标元素的示例代码：

function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

在上面的代码中，我们使用了左右两个指针，分别命名为left和right。通过不断调整两个指针的位置，我们可以缩小查找范围，直到找到目标元素或确定目标不存在。

4. 对撞指针

对撞指针也是双指针技巧中常见的一种。它通常用于解决数组中的问题，如判断数组中是否存在两个数的和等于目标值、在有序数组中查找两个数的和等于目标值等。

以下是一个使用对撞指针判断数组中是否存在两个数的和等于目标值的示例代码：

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

  while (left < right) {
    let sum = nums[left] + nums[right];

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

  return [];
}

在上面的代码中，我们使用了对撞两个指针，分别从数组的两端开始，通过不断调整两个指针的位置，我们可以找到满足条件的两个数。