前言

在引入大佬笔记之前，先说说我刷了这么多题对双指针的理解。双指针算法可以解决很多问题，我们把双指针分为很多类：

• 快慢指针

• 左右指针

  1. 左右指针
  2. 二分查找

• 滑动窗口

资料：

• 来自labuladong对滑动窗口的总结链接

• 来自labuladong对二分查找的总结链接

下面是 labuladong 对双指针做了首诗，如下：

滑动窗口

下面是滑动窗口大致的思路：

HashMap<Character,Integer> window = new HashMap<>();
int left = 0, right = 0;
while (right < s.length()){
    // 增大窗口
    window.put(s.charAt(right),right);
    right++;
    
    // 到达 边界 时，缩小窗口
    while (window needs shrink) {
        window.remove(s.charAt(left));
        left++;
    }
}

对于滑动窗口思想，我们要注意两个地方：

• 什么时候增大窗口
• 什么时候缩小窗口

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

下面是滑动窗口算法框架：

public void slidingWindow(String s,String t) {
    // 当前窗口
    HashMap<Character,Integer> window = new HashMap<>();
    // 需求
    HashMap<Character,Integer> needs = new HashMap<>();
    // 记录所需的元素
    for (int i = 0; i < t.length(); i++) {
        needs.put(t.charAt(i),needs.getOrDefault(t.charAt(i),0)+1);
    }
    // 滑动窗口 指针
    int left = 0, right = 0;
    int valid = 0;
    while(right < s.length()){
        char c = s.charAt(right);
        // 增大窗口
        window.put(c,window.getOrDefault(c,0)+1);
        right++;
        
        // 进行窗口内数据的一系列更新
        // todo ...
        
        // 判断是否缩小窗口
        while(window needs shrink){
            char d = s.charAt(left);
            left++;

            // 进行窗口内数据的一系列更新
            // todo ...
        }
    }
}

左右指针

提到左右指针，我们首先会想到的就是二分查找，对于二分查找也有多种场景：

• 寻找一个数
• 寻找左侧边界
• 寻找右侧边界

二分查找框架（基础）

public int binarySearch(int[] nums,int target) {
    // 定义左右指针
    int left = 0, right = nums.length-1;
    // 限制边界范围
    while( ... ) {
        int mid = (right - left)/2 + left;
        if(nums[mid] == target){
            // todo ...
        }else if (nums[mid] < target){
            // todo ...
        }else if (nums[mid] > target){
            // todo ...
        }
    }
    return // todo 下标;
}

代码中left + (right - left) / 2就和(left + right) / 2的结果相同，但是有效防止了left和right太大直接相加导致溢出。

寻找一个数（基本的二分搜索）

给你一个场景：给你一个有序的数组，判断数组是否存在target目标数。

我们根据上面的基础框架，可以得出：

public int binarySearch(int[] nums,int target) {
    int left = 0, right = nums.length-1;
    while (left <= right){
        int mid = (right - left)/2 + left;
        if (nums[mid] == target){
            return mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

下面有几个核心疑问：

1、while (left <= right) 这里我们使用的是 <= ,而不是< ?

我们在实现 二分查找 的时候， 我们会发现其实我们既可以使用 <=， 也可以使用 <, 那我们什么时候使用呢？ 我是这么理解的：

是否选择 = 其实与边界有关，那么与边界有关的两个变量就是left 和 right 的。 while中的区间其实就是我们进行搜索的区间。 我们在初始化变量的时候，有时候会将right 初始化为 nums.length, 有时候会初始化为 nums.length-1。两者的区别就是 开区间 和 闭区间 的区别。 如果 right = nums.length， 就是闭区间。显然会出现索引越界的问题，所以我们选择 < 。

再看一下labuladong的解释：

如果非要使用 while(left < right) 也是可以的。

// todo ...
while(left < right) {
    // todo ...
}
return nums[left] == target ? left : -1;

2、为什么 left = mid + 1，right = mid - 1？我看有的代码是right = mid或者left = mid，没有这些加加减减，到底怎么回事，怎么判断？

那么当我们发现索引mid不是要找的target时，下一步应该去搜索哪里呢？

当然是去搜索[left, mid-1]或者[mid+1, right]对不对？因为mid已经搜索过，应该从搜索区间中去除。

寻找左侧边界的二分搜索

对于寻找左侧边界，我们要特别注意缩小右侧边界， 以防我们由于缩小右侧边界的范围过大， 错过了左侧的边界。 看一下下面的情况。

当 nums[mid] >= target 时，可以看出我们可以统一 right = mid; 在一个疑问： 为什么 right 不是 mid - 1;

看一下上面的红色箭头（right = mid -1) 和 黄色(right = mid) 箭头。

这里就可以体现为什么不用 mid - 1 了。当nums[mid]被检测之后，下一步的搜索区间应该去掉mid分割成两个区间，即[left, mid)或[mid + 1, right)。

结束条件就是当 left >= right 时,结束条件。接下来是代码：

public int left_bound(int[] nums, int target) {  
    if (nums.length == 0) return -1;  
    int left = 0;  
    int right = nums.length; 
    while (left < right) { 
        int mid = (left + right) / 2;  
        if (nums[mid] == target) {  
            right = mid;  
        } else if (nums[mid] < target) {  
            left = mid + 1;  
        } else if (nums[mid] > target) {  
            right = mid; 
        }  
    }  
    return left;  
}

寻找右侧边界的二分查找

public int right_bound(int[] nums, int target) {  
    if (nums.length == 0) return -1;  
    int left = 0, right = nums.length;  
    while (left < right) {  
        int mid = (left + right) / 2;  
        if (nums[mid] == target) {  
            left = mid + 1;  
        } else if (nums[mid] < target) {  
            left = mid + 1;  
        } else if (nums[mid] > target) {  
            right = mid;  
        }  
    }  
    return left - 1; // 注意  
}

与找左边界其实思想是一样的，因为我们要找的是边界，所以当 nums[mid] == target 的时候，不会立刻返回，而是继续缩小选择区间，也就是 left = mid + 1 ;

后面 labuladong 的大佬对这三种进行了总结：

int binary_search(int[] nums, int target) {  
    int left = 0, right = nums.length - 1;   
    while(left <= right) {  
        int mid = left + (right - left) / 2;  
        if (nums[mid] < target) {  
            left = mid + 1;  
        } else if (nums[mid] > target) {  
            right = mid - 1;   
        } else if(nums[mid] == target) {  
            // 直接返回  
            return mid;  
        }  
    }  
    // 直接返回  
    return -1;  
}  
  
int left_bound(int[] nums, int target) {  
    int left = 0, right = nums.length - 1;  
    while (left <= right) {  
        int mid = left + (right - left) / 2;  
        if (nums[mid] < target) {  
            left = mid + 1;  
        } else if (nums[mid] > target) {  
            right = mid - 1;  
        } else if (nums[mid] == target) {  
            // 别返回，锁定左侧边界  
            right = mid - 1;  
        }  
    }  
    // 最后要检查 left 越界的情况  
    if (left >= nums.length || nums[left] != target)  
        return -1;  
    return left;  
}  
  
  
int right_bound(int[] nums, int target) {  
    int left = 0, right = nums.length - 1;  
    while (left <= right) {  
        int mid = left + (right - left) / 2;  
        if (nums[mid] < target) {  
            left = mid + 1;  
        } else if (nums[mid] > target) {  
            right = mid - 1;  
        } else if (nums[mid] == target) {  
            // 别返回，锁定右侧边界  
            left = mid + 1;  
        }  
    }  
    // 最后要检查 right 越界的情况  
    if (right < 0 || nums[right] != target)  
        return -1;  
    return right;  
}

快慢指针

下面是快慢指针的一个套路, 其实和滑动窗口的思想有点像

int slow = 0, fast = 0;
while(fast < nums.length){
    if ( ... ){
        // todo 缩小范围
        slow++;
    }
    // todo ... 扩大范围
    fast++;
}

对于快慢指针经常用于解决 删除重复元素 的场景

除了数组中会遇到快慢指针，其实这个技巧更多的是体现在解决链表问题的时候。分别由下面的场景：

• 判定链表中是否含有环
• 已知链表中含有环，返回这个环的起始位置
• 寻找链表的中点
• 寻找链表的倒数第n个元素
• 删除链表重复元素