Skip to content
On this page

1. 双指针

  1. 快慢指针-【链表】
    • 判定链表是否由闭环
    • 链表中点二分
    • 链表
    • 归并排序
  2. 左右指针-【数组/字符串】
    • 【有序】数组/字符串,二分搜索
    • 反转数组
  3. 滑动窗口

2. 如何判断是双指针

3. 双指针步骤

快慢指针

  1. 快慢指针初始化在头节点head
  2. 前进时fast在前,slow在后

左右指针

  1. 左指针left初始边缘0,右指针right初始数组最大边缘length-1
  2. left <(=) right时循环调用,取两者中间坐标赋给left或right

3. 双指针框架

快慢指针

js
var hasCycle = function(head) {
    var fast = head,
    slow = head;

    while(fast && fast.next) { // 判断fast及其下一个节点
        fast = fast.next.next // 重点:fast前进2 slow前进1
        slow = slow.next
        
        if(fast === slow) {
            return true
        }
    }
    return false
};

左右指针

js
var twoSum = function(numbers, target) {
    var left = 0,
    right = numbers.length - 1

    while(left < right) { // 如果左右指针不允许选择同一个元素重复利用,则不可以相等
        var sum = numbers[left] + numbers[right]
        if(sum === target) {
            return [left + 1, right + 1]
        } 

        if(sum < target) { // 重点:根据条件控制左指针或右指针变动
            left++
        } else {
            right--
        }
    }
    return null
};

4. 细化问题点

4.1 时间复杂度低,O(N)

根据其框架逻辑,循环一次depth增加一次,找到终点时能保证距离最短。最坏情况下在满二叉树时,从根节点起点,找底层最后一个树节点时,就需要全部节点穷举过,所以是O(N) DFS也是O(N),但永远都是需要所有分叉都走完才能对比,实际比BFS慢很多。BFS是面,DFS是线。BFS是集体行动,DFS是单打独斗。

4.2 空间复杂度高,为O(N)

空间复杂度为O(N)。最坏情况下在满二叉树时,存了最底部的树节点N/2,所以最坏空间复杂度O(N)。而DFS是递归,是一条线,最坏情况下也是树的高度,即O(logN)

4.3 双向BFS-优化

从起点和终点同时扩散,相遇(有交集)时停止。最坏时还是O(N),但实际中,如果是起点根节点,满二叉树底部的中间终点,便只要遍历半棵树。

总结

  1. BFS与DFS
    • BFS的实际时间复杂度低,但空间复杂度高,而DFS相反。
    • 时间复杂度
      BFS: O(N)
      DFS: O(N)
    • 空间复杂度
      BFS: O(N)
      DFS: O(logN)

课后疑问s

参考资料