双指针简介

双指针算法是一种通过设置两个指针不断进行单向移动来解决问题的算法。
它包含两种形式：快慢指针和对撞指针。
快慢指针是一种设置步长不同的两个指针，用于解决链表中的问题，如判断是否有环，找到中间节点等。
对撞指针是一种设置在序列两端向中间移动的两个指针，用于解决数组中的问题，如找到两数之和，反转元音字母等。
双指针算法的核心思想是利用单调性或者有序性，减少不必要的遍历，优化时间复杂度。下面我们将分别介绍这两种形式的双指针算法，并给出一些例题和解析。

快慢指针

快慢指针介绍

快慢指针是一种设置步长不同的两个指针，用于解决链表中的问题，如判断是否有环，找到中间节点等。
快慢指针的基本思想是让一个指针每次移动一步，另一个指针每次移动两步，这样当两个指针相遇时，就可以得到一些有用的信息。下面我们将通过一些例题来展示快慢指针的用法和技巧。

快慢指针例题

例题1：判断链表是否有环

给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

思路：我们可以使用快慢指针来解决这个问题。首先，我们定义两个指针 fast 和 slow ，并让它们都指向链表的头节点。然后，我们让 fast 每次移动两个节点，slow 每次移动一个节点。如果链表中没有环，那么 fast 最终会遇到空节点，结束循环。如果链表中有环，那么 fast 和 slow 最终会在环内相遇，也结束循环。我们只需要判断循环结束时 fast 和 slow 是否相等，就可以知道链表是否有环。

代码：

public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
例题2：找到链表的中间节点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

思路：我们可以使用快慢指针来解决这个问题。首先，我们定义两个指针 fast 和 slow ，并让它们都指向链表的头节点。然后，我们让 fast 每次移动两个节点，slow 每次移动一个节点。当 fast 到达链表的末尾时，slow 就恰好在链表的中间节点。如果链表的长度是偶数，那么 fast 会停在最后一个节点的后面，此时 slow 在中间两个节点的前面一个，我们需要返回 slow 的下一个节点。

代码：

public ListNode middleNode(ListNode head) {
  
  if (head == null || head.next == null) {
  
    return head;
  }
  ListNode fast = head;
  ListNode slow = head;
  while (fast != null && fast.next != null) {
  
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
}

快慢指针优缺点：

快慢指针是一种常用的优化技巧，它有以下的优点：

它可以在不使用额外空间的情况下，解决一些链表或数组的问题，如判断是否有环，找到中间节点，找到倒数第k个节点等。
它可以在一次遍历中，得到一些有用的信息，如环的长度，环的入口，链表的长度等。
它可以简化代码的逻辑，避免使用多重循环或递归。

快慢指针也有一些缺点，如：

它需要对链表或数组的结构有一定的了解，才能正确地设置快慢指针的步长和终止条件。
它可能会遇到一些边界情况，如链表为空，链表只有一个节点，链表长度为偶数或奇数等，需要特别注意处理。
它可能会造成一些误解或困惑，如快慢指针相遇时，它们是否在环的入口，是否在环的中点，是否在链表的中点等。需要仔细分析和证明。

对撞指针

对撞指针介绍：

对撞指针是一种设置在序列两端向中间移动的两个指针，用于解决数组中的问题，如找到两数之和，反转元音字母等。对撞指针的核心思想是利用数组的有序性，根据两个指针所指元素的和与目标值的大小关系，决定移动哪个指针，从而减少不必要的遍历，优化时间复杂度。下面我们将通过一些例题来展示对撞指针的用法和技巧。

对撞指针例题

例题1：找到两数之和

给定一个已按照升序排列的有序数组 nums ，和一个目标值 target 。请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

假设每种输入只会对应一个答案，但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums1 == 9 ，返回 [0, 1] 。示例 2：

输入：nums = [2,3,4], target = 6 输出：[0,2] 示例 3：

输入：nums = [-1,0], target = -1 输出：[0,1]
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

思路：我们可以使用对撞指针来解决这个问题。首先，我们定义两个指针 left 和 right ，并让它们分别指向数组的首尾元素。然后，我们计算 left 和 right 所指元素的和 sum ，并与目标值 target 比较。如果 sum 等于 target ，那么我们就找到了答案，返回 left 和 right 的下标。如果 sum 小于 target ，那么我们就让 left 向右移动一位，增大 sum 的值。如果 sum 大于 target ，那么我们就让 right 向左移动一位，减小 sum 的值。我们重复这个过程，直到找到答案或者 left 和 right 相遇。

代码：

public int[] twoSum(int[] numbers, int target) {
  
  if (numbers == null || numbers.length < 2) {
  
    return new int[0];
  }
  int left = 0;
  int right = numbers.length - 1;
  while (left < right) {
  
    int sum = numbers[left] + numbers[right];
    if (sum == target) {
  
      return new int[]{
  left + 1, right + 1};
    } else if (sum < target) {
  
      left++;
    } else {
  
      right--;
    }
  }
  return new int[0];
}

例题2：反转元音字母

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

示例 1：

输入：“hello” 输出：“holle” 示例 2：

输入：“leetcode” 输出：“leotcede”

思路：我们可以使用对撞指针来解决这个问题。首先，我们定义两个指针 left 和 right ，并让它们分别指向字符串的首尾字符。然后，我们判断 left 和 right 所指字符是否都是元音字母（a,e,i,o,u）。
如果是，那么我们就交换 left 和 right 所指字符的位置，然后让 left 向右移动一位，right 向左移动一位。如果不是，那么我们就让不是元音字母的指针向中间移动，直到找到元音字母或者 left 和 right 相遇。

代码：

public String reverseVowels(String s) {
  
  if (s == null || s.length() < 2) {
  
    return s;
  }
  char[] chars = s.toCharArray();
  int left = 0;
  int right = chars.length - 1;
  String vowels = "aeiouAEIOU";
  while (left < right) {
  
    if (!vowels.contains(chars[left] + "")) {
  
      left++;
    } else if (!vowels.contains(chars[right] + "")) {
  
      right--;
    } else {
  
      char temp = chars[left];
      chars[left] = chars[right];
      chars[right] = temp;
      left++;
      right--;
    }
  }
  return new String(chars);
}

对撞指针优缺点：

对撞指针有以下的优点：

它可以在不使用额外空间的情况下，解决一些有序数组的问题，如找到两数之和，反转元音字母等。
它可以在一次遍历中，得到一些有用的信息，如数组中是否存在满足条件的元素对，反转后的字符串等。
它可以简化代码的逻辑，避免使用多重循环或二分查找。

对撞指针也有一些缺点，如：

它需要对数组的有序性有一定的了解，才能正确地设置对撞指针的移动方向和终止条件。
它可能会遇到一些边界情况，如数组为空，数组只有一个元素，数组中没有满足条件的元素对等，需要特别注意处理。
它可能会造成一些误解或困惑，如对撞指针相遇时，它们是否在数组的中点，是否在满足条件的元素对的最小或最大位置等。需要仔细分析和证明。

算法详解-双指针算法的魅力-一种简单而高效的编程思想