双指针

# 双指针

双指针主要用于遍历数组或者链表，两个指针指向不同的元素，从而协同完成任务。

但是双指针并不隶属于某一种数据结构，无论是数组、链表、字符串等元素都会运用到双指针，而且双指针的提醒在面对中小型的公司，也是笔试的常客。

双指针主要分为两大类: 左右指针和快慢指针。

左右指针:

两个指针相向而行 -> <-
快慢指针:

两个指针同向而行，一快一慢 -> ->>

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个。

伪代码如下:

function fn(list) {
        var slow = 0;
        var fast = 0;
        while (fast < list.length){
	    slow++;
	    fas
        }
        return slow+1;
    }

左右指针是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。

左右对撞适用于有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用左右指针解题

function fn (list) {
  var left = 0;
  var right = list.length - 1;

  //遍历数组
  while (left <= right) {
    left++;
    // 一些条件判断 和处理
    ... ...
    right--;
  }
}

‍