何为双指针
我们来看看leetcode的解释
双指针从广义上来说，是指用两个变量在线性结构上遍历而解决的问题。狭义上说，
- 对于数组，指两个变量在数组上相向移动解决的问题；
- 对于链表，指两个变量在链表上同向移动解决的问题，也称为「快慢指针」问题。
双指针算法通常不难，双指针算法是基于暴力解法的优化，它们是很好的学习算法的入门问题
双指针经典题型
我们来看看有哪些经典的双指针问题
1. 指针相向查找
leetcode-977 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100] 复制代码
由于元素排列是有序的，而且存在负数，所以元素的平方可能先减小后增大。如何按照普通遍历方式，每次还得查找元素平方后的插入位置，需要用到双循环来处理。而利用双指针，可以很好的利用题目条件，元素的升序排列，每次比较左右元素的绝对值大小即可。
var sortedSquares = function(nums) { let left = 0 let right = nums.length - 1 const ans = [] while(right >= left) { const leftNum = nums[left] const rightNum = nums[right] if (rightNum + leftNum >= 0) { ans.unshift(Math.pow(rightNum, 2)) right-- } else { ans.unshift(Math.pow(leftNum, 2)) left++ } } return ans }; 复制代码
leetcode-167 两数之和 II - 输入有序数组
有序数组求两数之和是经典的双指针题型了
给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。 复制代码
思路很简单，利用数组升序排列，求左右指针元素和，如果大于目标值则左移右指针，否则右移动左指针。当和为目标值时取得答案退出搜索。
var twoSum = function(numbers, target) { let left = 0 let right = numbers.length - 1 let ans = [] while(right > left) { let num1 = numbers[left] let num2 = numbers[right] if (num1 + num2 === target) { ans = [left + 1, right + 1] break } if (num1 + num2 > target) { right-- } else { left++ } } return ans }; 复制代码
学习完两数之和的可以继续挑战下三数之和，属于一样的题型。
leetcode-11 盛最多水的容器
这题是个经典的双指针面试题
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
示例 1：
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 复制代码
var maxArea = function(height) { let left = 0 let right = height.length - 1 let ans = 0 while(right > left) { const leftH = height[left] const rightH = height[right] // 舍弃当前较短边 if (leftH > rightH) { ans = Math.max( ans, rightH * (right - left) ) right-- } else { ans = Math.max( ans, leftH * (right - left) ) left++ } } return ans }; 复制代码
2. 指针同向查找
leetcode-283 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 复制代码
我们使用双指针同向移动可以做到操作原数组就解决此问题，左指针指向未排序的元素，其元素值可能为0，右指针指向遍历元素。
var moveZeroes = function(nums) { let left = 0 let right = 0 let len = nums.length while(right < len) { if (nums[right]) { // 当左右指针相等时说明前面都是已经非0元素 if (right === left) { left++ right++ continue } // 交换左右指针元素 const temp = nums[right] nums[right] = nums[left] nums[left] = temp left++ } // 无论右指针元素是否为0都+1 right++ } return nums } 复制代码
3. 快慢指针
链表的双指针题型一般为快慢指针的应用。
leetcode-876 链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
var middleNode = function(head) { let fast = head let slow = head // 快指针每次移动两格 慢指针移动一格 // 如此当快指针移动到末端时就可以取的慢指针为中间节点 while(fast.next && fast.next.next) { fast = fast.next.next slow = slow.next } // 根据题目要求返回第二个中间节点 if (fast.next) { slow = slow.next } return slow }; 复制代码
leetcode-19 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
var removeNthFromEnd = function(head, n) { let first = new ListNode('', head) let fast = head let slow = first // 同样是利用快慢指针 // 这次不是中间节点，而是倒数第n个 // 于是我们先让快指针快n步 for (let i = 0; i < n; i++) { fast = fast.next } // 此时快慢指针等步移动 // 我们或许也可称之为前后指针 while(fast) { fast = fast.next slow = slow.next } slow.next = slow.next.next return first.next }; 复制代码
总结
双指针的问题多见于数组或链表的数据结构中，数组中分为相向指针和同向指针，而链表中多为快慢指针。一般使用双指针可以优化算法，得出相对暴力算法的更优解。
