算法总结-双指针

发表于   |   分类于   |     |   阅读次数

当需要遍历数组或者字符串并从中找出满足条件的子集或者子串的时候，简单的方法就是使用嵌套的循环来实现，但是这样的实现通常时间复杂度会太高，此时就可也考虑使用双指针来对算法进行优化。双指针顾名思义，就是需要应用到、两个指针，一个指针在前一个指针在后，通过移动这两个指针来找到满足条件的解。

LeetCode15

题目链接：
https://leetcode.com/problems/3sum/

题目描述：
从一个数组中找出所有不重复的三元组，每个三元组中的数字之和为0。

例子

1
2
3
4
5
6
7
数组 nums = [-1, 0, 1, 2, -1, -4],

满足条件的解:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题目分析：
用三个for循环可以很容易将算法写出来，但是那样的话时间复杂度为O(N3)，很不理想。这时就可以应用到双指针了。首先需要将数组进行排序，一方面便于使用双指针进行查找，另一方面便于跳过重复的数字。然后再遍历整个数组来寻找合法三元组的第一个数。

如下所示,对于每个数 i，在其右边剩下的数中使用两个指针 j 和 k 分别从前后相向进行遍历，查找满足条件的三元组。这样优化后，算法的整体复杂度为O(N2)，比之前降低了一个数量级

1
2
3
 i→
-4, -1, -1, 0, 1, 2
	j→        ←k

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end()); //数组排序
    for(int i = 0; i < nums.size(); i++) {
        if(i > 0 && nums[i] == nums[i - 1]) continue; //跳过重复的数字
        int j = i + 1, k = nums.size() - 1;
        while(j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if(sum == 0) {//找到一个满足条件的三元组
                result.push_back({nums[i], nums[j], nums[k]});
                //跳过与nums[j]和nums[k]重复的数字
                while(j < k && nums[j] == nums[j + 1]) j++;
                while(j < k && nums[k] == nums[k - 1]) k--;
                j++;
                k--;
            } else if(sum > 0) { //和大于零，通过将k往左边移动来减少和。
                k--;
            } else { //和小于零，通过将j往右边移动来增加和。
                j++;
            }
        }
    }
    return result;      
}

LeetCode19

题目链接：

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

题目描述：

从一个单链表中删除倒数第n个节点，并返回删除这个节点后链表的头节点。n一定是个有效的数字。

例子

1
2
3
给定链表: 1->2->3->4->5, n = 2.

删除倒数第2个节点后链表变成: 1->2->3->5.

题目分析：

一个简单的算法就是首先遍历一遍整个链表，记录下链表的长度，然后再次遍历并计数，根据链表的长度计算出需要删除的节点的位置并将其删除。但是这样就需要遍历链表两次，使用双指针就可以在只遍历一次的基础上删除该节点。

使用双指针解决链表相关的问题时，可以将其想象成两个人赛跑。小学应用题来了：甲乙这两个人跑得一样快，让甲先跑n步，然后乙再出发，当甲到达终点的时候，乙离终点有多远呢？如果会做这道应用题，那么解这个题目的算法就不难写出来了。只是需要注意如果倒数第n个节点恰好是头结点这个特殊情况。此外，该方法还可以应用在判断链表是否有环等题目上。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *left = head, *right = head;
    while(n-- > 0) { //right先往前走n步
        right = right->next;
        if(!right){ //right已经到达了终点，说明要删除的就是头节点，此时直接返回第二个节点即可
            return  head->next;
        }
    }
    while(right->next) { left和right同步往终点走
        left = left->next;
        right = right->next;
    }
	//left的下个节点就是倒数第n的节点，将其删除。
    left->next = left->next->next;
    return head;
}

LeetCode42

题目链接：

https://leetcode.com/problems/trapping-rain-water/

题目描述：

给定一个非负整数数组代表各个竖条的高度，每个竖条的宽度都为1。计算出下完雨后，所有竖条组成的容器最多可以盛多少雨水。如数组[0,1,0,2,1,0,1,3,2,1,2,1]及其能盛的最多的水为6。具体可以参考下图。

题目分析：
这是一道困难级别的题目。可以对每个竖条进行单独分析。如果一个竖条上想要存上水，则在其两侧必然都有比其高的竖条作为边。而这个竖条上能存的最多的水则是由其左侧最高的边和右侧最高的边中最低那个决定的。如上图中中间那个高度为0的竖条，其左侧最高的为2，右侧最高为3，所以这个竖条之上最多可以盛的水为2。

具体算法的实现可以使用双指针分别指向数组的两端，然后将低边向高边移动，同时记录下当前最高的边，计算出每个竖条上能盛的水并记录下来即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int trap(vector<int>& height) {
	int sum = 0, maxLeft = 0, maxRight = 0;//maxLeft和maxRight分别记录下左右两边最高的边
	int left = 0, right = height.size() - 1;
	while(left < right) {
	    if(height[left] < height[right]) {//左侧的较低
	        if(height[left] < maxLeft) {//当前的竖条小于左侧的最高边，计算能盛的水量
	            sum += maxLeft - height[left];
	        } else {
	            maxLeft = height[left];//当前竖条较高，无法盛水，将其最为一个边
	        }
	        left++;//左侧较低，向较高的右侧移动
	    } else {//右侧的较低
	        if(height[right] < maxRight) {
	            sum += maxRight - height[right];
	        } else {
	            maxRight = height[right];
	        }
	        right--;
	    }
	}
	return sum;
}

总结

双指针就是应用两个指针同向或者逆向按照一定的条件进行移动来找出解的方法。在应用双指针的时候要考虑清楚指针的起始位置、移动方向和移动条件。此外双指针还有一些具体的应用如滑动窗口等将在后文中进行研究。
signature.png