每天一种算法（三） –双指针算法-一一网

双指针算法

什么是双指针算法？

双指针算法是一种常见的算法，核心理念是使用两个指针，分别指向不同的元素，通过对比指向的元素来协同完成任务。

若两个指针指向同一数组，遍历方向相同且不会相交，则称为滑动窗口，用于解决区间搜索问题。

若两个指针指向同一数组，遍历方向相反，则可以用来搜索有序数组（需要提前进行排序）。

还有快慢指针，可以用来判断链表环路问题。

我们来看一个简单的例子，来了解如何使用双指针算法来解决问题：

找到数组中和为定值的两个元素（对应leecode 第167题）

问题描述：

给定一个已按照升序排列的整数数组 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 。
复制代码

解题思路：

这道题比较简单，首先我们已知是一个升序排列的整数数组，然后要找到相加之和等于目标数target的两个数。我们利用双指针法，一个指针指向数组头部，一个指针指向数组尾部，比较头尾指针指向的元素之和sum与目标数target，如果sum大于target，那我们应该把sum往下减，即把尾部指针往回退；如果sum小于target，那我们应该把sum往上加，即把头部指针往前移。直到两个指针相遇或找到了满足条件的指针（即sum === target），结束遍历。以示例1为例，我们来看具体步骤：

头部指针l指向下标为0的元素2，尾部指针r指向下标为3（length-1）的元素15，我们把 l 和 r 相加，得到结果17，大于target 9，我们把尾部指针往回退（r–）。
此时l指向下标0，r指向下标2，l+r的和为13，大于target 9，我们继续往回退。
此时l指向下标0，r指向下标1，l+r的和为9，等于target 9，我们得到题解。

js代码实现：

var twoSum = function(numbers, target) {
    let l = 0, r = numbers.length - 1;
    while(l < r) {
        if(numbers[l] + numbers[r] === target) {
            // 注意：这里是因为题目告诉我们下标是从1开始的，所以要把数组的下标+1
            return [l + 1, r + 1];
        }
        if(numbers[l] + numbers[r] > target) {
            r--;
        }
        if(numbers[l] + numbers[r] < target) {
            l++;
        }
    }
}
复制代码

分析时间复杂度：

核心代码（即每次指针移动）遍历了n次，是线性时间的时间复杂度。

所以时间复杂度是O(n)。

归并两个有序数组（对应leecode 第88题）

问题描述：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

输入输出示例

// 示例1

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

输出：[1,2,2,3,5,6]
复制代码

解题思路：

我们要把两个有序数组合并，我们可以声明两个指针，分别指向nums1和nums2的尾部。我们比较两个指针指向的元素，把大的那一个放到nums1的 m + n – 1 位置（nums1和nums2的数组总长度为m + n，减一是下标）。然后把大的元素所在的数组指针往前移。如果nums2遍历完了，而nums1没有，结束遍历，不需要再做处理。如果nums1遍历完了，而nums2没有，把所有的nums2的元素移到nums1的对应位置。

js代码实现：

分析时间复杂度：

核心代码（即每次指针移动）共遍历了m+n次，是线性时间的时间复杂度。

所以时间复杂度是O(m+n)。

快慢指针（对应leecode 第142题）

问题描述：

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

输入输出示例

截屏2021-05-24 下午3.40.36.png

示例1：

输入：head = [3,2,0,-4], pos = 1

输出：返回索引为 1 的链表节点

解释：链表中有一个环，其尾部连接到第二个节点。
复制代码

解题思路：

这里主要是要理解链表的特性。我们知道链表是类似{ val, next }的数据结构，所以上述图片和示例我们可以映射为代码：

// 链表的实现：

function ListNode(val) {
    this.val = val;
    this.next = null;
}

var listNode1 = new ListNode(3);
var listNode2 = new ListNode(2);
var listNode3 = new ListNode(0);
var listNode4 = new ListNode(-4);

listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode2;
复制代码

对于链表找环路的问题，有一个通用的解法：快慢指针。思路是：

给定两个指针，分别命名为slow和fast，起始位置在链表的开头。
fast每次走两步，slow每次走一步。
如果fast可以走到尽头，表示没有环路。
如果fast可以无限走下去，说明一定有环路，且一定存在一个时刻slow和fast会相遇。
当slow和fast第一次相遇时，将fast重新移动到链表开头，并让slow和fast每次都前进一步。
当slow和fast第二次相遇时，相遇的节点即为环路的开始点。

js代码实现：

var detectCycle = function(head) {
    let fast = slow = head;
    while(true) {
        if(!fast || !fast.next) {
            return null;
        }
        fast = fast.next.next;
        slow = slow.next;
        if(fast === slow){
            break;
        }
    }
    fast = head;
    while(fast !== slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}
复制代码

快慢指针的数学分析

fast和slow都指向链表头部，fast每轮走2步，slow每轮走1步。当fast可以走到链表末端时（即fast === null 或 fast.next === null），表明链表没有环路。
若fast不能走到链表末端，则fast和slow一定会相遇。（若有环，fast每次比slow多走1步，即没走一轮fast和slow的间距都会+1，fast一定会追上slow）
当fast和slow相遇时，设fast走了f步，slow走了s步。我们把链表从环路开始的位置切割开，将没有环路的链表长度记为a, 环路部分的链表长度记为b，则链表总长度是a+b。我们假设在fast和slow相遇时，fast比slow多走了n轮个b，这时f和s的关系如下：

式1: f = 2s; // fast每次走的步数是slow的2倍，它们相遇时f是s的2倍。

式2: f = s + nb; // fast和slow相遇时，fast比slow多走了n个b。

式1 – 式2 得: s = nb, f = 2nb;

也就是说：当fast和slow相遇时，fast走了 2n 个环，slow走了 n 个环。

我们将总步数记为k，则：走到链表的环的入口的步数是 a + nb。目前 slow 已经走了 nb 步，我们只需要让 slow 再走 a 步停下，就可以找到环的入口了。
我们把fast重新指向header，让fast和slow同时每轮向前走一步。当fast和slow相遇时，fast走了 a 步，slow走了 a + nb 步，即找到题解。

分析时间复杂度：

核心代码（即每次指针移动）共遍历了n次，是线性时间的时间复杂度。

所以时间复杂度是O(n)。

滑动窗口（对应leecode 第76题）

问题描述：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

输入输出示例

// 示例1

输入：s = "ADOBECODEBANC", t = "ABC"

输出："BANC"
复制代码

解题思路：

滑动窗口的思路是：先把指针的尾部往后移动，直到满足限制条件；然后固定尾部指针，移动头部指针，直到刚好不满足限制条件；然后继续移动尾部指针、移动头部指针…直到终止。

结合上述示例，我们来做分析：

先将题目描述转换，我们要在s中找到覆盖t所有字符的最小子串，是不是可以理解为：t中的所有不同字符出现的次数小于等于它们在最小子串中出现的次数？所以我们第一步先找出t中所有不同的字符以及它们出现的次数，并记录在一个对象map中。这里我们使用一个辅助函数来处理。我们得到结果：
```
map = {
    A: 1,
    B: 1,
    C: 1
}
复制代码
```
确定了t中的不同字符以及它们出现的次数，我们把尾部指针往前移动，直到覆盖t所有字符（即map中的每一项及value都在首尾之间）
```
// 头部指针不变（为0），尾部指向下标5，此时子串为'ADOBEC'
l = 0, r = 5, str = 'ADOBEC'
复制代码
```

固定尾部指针，接着移动头部指针，直到刚好不能覆盖t中所有字符。记录当前下标及长度。

// 固定尾部指针（为5），接着移动头部指针至下标1，此时子串为'DOBEC'，记录头部指针的上一个位置0，长度为5-0+1 = 6（前闭后开[)）
l = 1, r = 5, str = 'DOBEC', start = 0, len = 6
复制代码

再次移动尾部指针，直到覆盖t所有字符

// 头部指针不变（为1），尾部指向下标10，此时子串为'DOBECODEBA'
l = 0, r = 5, str = 'DOBECODEBA'
复制代码

固定尾部指针，接着移动头部指针，直到刚好不能覆盖t中所有字符。记录当前下标及长度。

// 固定尾部指针（为10），接着移动头部指针至下标6，此时子串为'ODEBA'，此时头部指针的上一个位置5，长度为5-0+1 = 6（前闭后开[)），对比长度，发现一致，不做改变
l = 5, r = 10, str = 'ODEBA', start = 0, len = 6
复制代码

再次移动尾部指针，直到覆盖t所有字符

// 头部指针不变（为6），尾部指向下标12，此时子串为'ODEBANC'
l = 6, r = 12, str = 'ODEBANC'
复制代码

固定尾部指针，接着移动头部指针，直到刚好不能覆盖t中所有字符。记录当前下标及长度。

// 固定尾部指针（为12），接着移动头部指针至下标10，此时子串为'ANC'，此时头部指针的上一个位置9，长度为12-9+1 = 4（前闭后开[)），对比长度，发现更小，改变下标和长度
l = 10, r = 12, str = 'ANC', start = 9, len = 4
复制代码

js代码实现：

// 辅助函数：找出t中所有不同的字符以及它们出现的次数，并记录在一个对象map中
function tMap(str) {
    const map = {}, type = 0;
    for(let i = 0; i < str.length; i++) {
        if(map[str[i]] !== undefined) {
            map[str[i]] ++;
        }
        else {
            map[str[i]] = 1;
            type++;
        }
    }
    return {map, type};
}

// 主函数
function minWindow(s, t) {
    const sLen = s.length, tLen = t.length;
    if(sLen < tLen) {
        return '';
    }
    let { map, type } = tMap(t);
    let l = 0, r = 0, start = 0, minLen = sLen + 1;
    while(r < sLen) {
        if(map[s[r]] !== undefined) {
            map[s[r]]--;
        }
        if(map[s[r]] === 0) {
            totalType--;
        }
        // 此时，子串中包含t所有字符，开始移动头部指针l
        while(totalType === 0) {
            // 更新最小窗口的起点和最小窗口长度
            if(r - l + 1 < minLen) {
                minLen = r - l + 1;
                start = l;
            }
            let leftChar = s[l];
            if(map[leftChar] !== undefined) {
                map[leftChar]++;
            }
            if(map[leftChar] > 0) {
                totalType++;
            }
            l++;
        }
        r++;
    }
    if(start === sLen) {
        return '';
    }
    return s.substring(start, start + minLen);
}
复制代码