卡尔白~ (@Karlbaey) 在 程序设计#4 - 【经典算法】双指针和滑动窗口·第一部分 中发帖
上期指路→
原文 URL 请到文末查看!感谢支持!
书接上回。
滑动窗口算法是双指针算法的变形,而且因为入门门槛低,我打算下一期就做这个了。
双指针算法(two-pointer algorithm)是处理序列(如数组、链表、字符串)的强大技巧。它通过维护两个指针(索引)来追踪序列中的某个范围或元素,从而高效地解决问题。
它尤其擅长解决子数组或子串的相关问题(特别是滑动窗口)。子数组就是一个完整数组里连续的一段,子串就是字符串里连续的一段。
对于输入所给的序列,尽管它们具有确定的顺序,但我们对它一无所知。除非使用索引 arr[i] 查询,否则永远也不可能一次性知道所有元素的位置。
这时候,如果我们身处一个序列中,就像是在一条漆黑的走廊里。运用暴力算法就像是一次只打开一盏灯,看当前位置的元素,然后穷举所有的可能结果。这样做的最坏时间复杂度可能超过 O(n2)。
换...