Day13:[解题技巧]Two pointers - 双指针

双指针算是一个解题蛮常用的小技巧，双指针指的是用两个指针对整个资料做遍历，而双指针又依照移动的方向性，分为对撞指针(反方向)和快慢指针(同方向)。

对撞指针

两个指针为相反方向，通常一个在起点，一个在终点，慢慢向中间靠拢，在起始点的通常命名为left，在终点是right，那麽就用经典的two sum来示范双指针吧!

注意:如果要用双指针解这题，阵列必须要是有依序排列过的

two sum的题目为给定一个阵列arr和目标数target，arr[x] +arr[y] = target，请回传arr[x], arr[y]

Example : 有一个排序过的阵列为[2, 3, 5, 9, 11]，请问阵列中的哪两个数字相加会等於目标数8呢?

实作步骤如下:
1.在起点设置左指针，在终点设置右指针

2.此时因为2+11 = 13 大於我们的目标数8，所以将右指针移动到9的位置

3.结果2+9 = 11，还是大於8 ，所以又把右指针移到5的位置

4.2+5 = 7 ，不幸的小於目标数8 ，所以把左指针移动到3，这时候就会发现3 、5这个组合不就是我们要找的吗?所以成功找到两个加起来总和为8的数字了!

用js实作双指针

const twoSum = (arr, target) => {
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
        if (arr[left] + arr[right] === target) {
            return [arr[left], arr[right]];
        }
        if (arr[left] + arr[right] > target) {
            right--;
        } else {
            left++;
        }
    }
    return null;
};

twoSum([2, 3, 5, 9, 11], 8);

快慢指针

可以想像是程序界的龟兔赛跑，两个指针的移动方向均为相同方向，但移动的速率为一快一慢。

题目范例:检查str2是否为str1的subSequence，str1 = forever love，str2 = love

实作步骤如下:

1.红色指针是快指针，黄色是慢指针，一开始两种指针都会在起始点

2.快指针每次都会移动一格，慢指针则是必须符合条件才会移动，移动条件:当快指针指向的字母与慢指针相同时

3.不幸的因为一直不符合条件，所以只有快指针一路往後走

4.好不容易，当快指针指到l，终於符合条件了!所以慢指针就可以前进一格

5.当慢指针指到最後一格的时候，就代表love的确是forever love的subSequence

用js实作快慢指针

const isSubsequence = (str1, str2) => {
    if (str1.length === 0) return true;

    let slow = 0;
    let fast = 0;

    while (fast < str2.length) {
        if (str1[slow] === str2[fast]) {
            slow++;
        }
        if (slow >= str1.length) {
            return true;
        }
        fast++;
    }
    return false;
};

isSubsequence("love", "forever love");

快慢指针的解题方法蛮常被运用在Linked List的题型上面，像是反转Linked List或是确认该Linked List是否有Cycle(如下图)

图片来源:leetcode 141. Linked List Cycle