双指针技巧汇总

发表于 | 分类于

双指针技巧

双指针技巧还可以分为两类，一类是「快慢指针」，一类是「左右指针」。前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。

快慢指针常见算法

判定单链表中是否含有环

bool hasCycle(ListNode head) {
  ListNode fast, slow;
  fast = slow = head;
  while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
    if (slow == fast) return true;
  }
  return false;
}

已知链表中含有环，返回这个环的起始位置

第一次相遇时，假设慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步，也就是说比 slow 多走了 k 步（也就是环的长度）

设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点

所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后就会相遇，相遇之处就是环的起点了。

ListNode detectCycle(ListNode head) {
	ListNode slow = head, fast = head;
  while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
    if (slow == fast) break;
  }
  
  slow = head;
  while (slow != fast) {
    slow = slow.next;
    fast = fast.next;
  }
  
  return slow;
}

寻找链表的中点

类似上面的思路，我们还可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。

ListNode midNode(ListNode head){
  ListNode slow, fast;
	slow = fast = head;
	while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
	}
	// slow 就在中间位置
	return slow;
}

寻找链表的倒数第 k 个元素

ListNode getKNode(ListNode head) {
  ListNode slow, fast;
  slow = fast = head;
  while (k-- > 0) 
      fast = fast.next;

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

左右指针常见算法

二分查找

参考二分搜索总结

两数之和（leetcode 167）

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

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

反转数组

void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        // swap(nums[left], nums[right])
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++; right--;
    }
}

滑动窗口算法

参考滑动窗口解题框架