算法-双指针 快慢指针

本文主要是介绍算法-双指针 快慢指针，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

双指针：

不同的状态，导致不同指针的移动。最终的状态由于两个指针的位置决定。

经典题目：

1. 盛最多水的容器

问题抽象，容量：

min(l, r) * t。

容量取决于最小的一块木板，并且和木板之间的距离有关。

另双指针在容器的各自最远端。双指针开始向内移动，最大的容量必定在向内移动的过程中产生。

因为向内移动必定减小t，此时向内移动的最优方向必定以去掉较小的一块木板决定。

因此往min(l, r)方向移动一次。

时间复杂度O(N)

2. 所有三数之和或者两数之和。

问题在于找到**所有**符合的元素。

如果只找一个，哈希表可以O(n)。

找到所有，先排序O(nlogn)，再双指针O(n)。

三数之和的时间复杂度为O(n*n)

这篇关于算法-双指针 快慢指针的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！