05-数据结构与算法
双指针法

双指针法理论基础

双指针法适用于各种数据结构，数组、链表、栈和队列等等，应用范围非常广泛，而且代码还比较简单。

双指针技巧总体可分为两类：

「左右指针」：主要解决数组（或者字符串）中的问题，比如字符串逆置等
「快慢指针」：主要解决链表中的问题，比如典型的判定链表中是否包含环。原地修改数组的问题一般也可以用快慢指针来解决。

左右指针类型中有一种**「滑动窗口」**算法，属于双指针中比较难的题目，这里我们给他单独划一类来讲。

# 1. 左右指针

左右指针在数组中实际是指两个索引值，一般初始化为 left = 0, right = nums.length - 1 。

二分查找就是一个非常典型的左右指针的应用。

代表题目：

# 2. 滑动窗口算法

滑动窗口算法是双指针里面最难的一部分，不过这个算法技巧的思路非仍然是左右指针的思想，就是维护一个窗口，不断滑动，然后更新答案。该算法的大致逻辑如下：

int left = 0, right = 0;
while (right < s.size()) {    
    // 增大窗口    
    int newNum = s[right];
    right++;
    // 增大窗口后对 window 进行处理
    window.add(newNum);  
    
    // window needs shrink
    while (window needs shrink) {        
        // 缩小窗口        
        int removeNum = s[left];       
        left++;    
        // 缩小窗口后对 window 进行处理
        window.remove(removeNum); 
    }
}

代表题目：

# 3. 快慢指针

快慢指针一般用来解决两个场景下的问题：

1）链表

快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。

代表题目：

2）原地修改数组

我们知道对于数组来说，在尾部插入、删除元素是比较高效的，时间复杂度是 O(1)，但是如果在中间或者开头插入、删除元素，就会涉及数据的搬移，时间复杂度为 O(N)，效率较低。

所谓原地修改，就是不允许我们 new 一个新的数组，只能在原数组上进行操作，然后返回结果。

如果不是原地修改的话，我们直接 new 一个 int[] 数组，把修改之后的元素放进这个新数组中，然后返回这个新数组即可。

解决这类原地修改数组的问题一般都可以使用快慢指针的思想。

代表题目：

🎁 公众号

各位小伙伴大家好呀，叫我小牛肉就行，目前在读东南大学硕士，上方扫码关注公众号「飞天小牛肉」，与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面

Last Updated: 2023/02/16, 11:27:10

← 找出有序数组中绝对值最小的数验证回文串→