信息技术大学
数组与双指针
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
数组与双指针
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
双指针两大套路（对撞/快
对撞从两头往中间挤，快慢一前一后追：两根指针省掉一层循环。
对撞
有序数组两数之和、回文判断，左右夹逼
快慢
移除元素、找中点找环，速度差定用途
原地操作
数组题先想双指针，空间 O(1) 是卖点
滑动窗口框架
右指针探路左指针收网：窗口内不满足就缩，满足就扩，一遍线性。
框架
右扩探索，违约左缩，窗口状态持续维护
状态维护
哈希计数窗口内元素，进出各更新一次
题型信号
「最长/最短子串子数组满足条件」即窗口
无重复字符最长子串
python
右扩左缩两根指针扫一遍，滑动窗口的经典模板。
代码高亮加载中…
右指针每走一步，左指针只在违约时收紧；窗口集合 O(1) 判重，整体 O(n)。
前缀和与差分
前缀和把区间求和降到 O(1)，差分把区间修改降到 O(1)，一对互逆的时空交换。
前缀和
pre[i] 存前 i 项和，区间和 = pre[r] − pre[l−1]
差分
diff[l]+x、diff[r+1]−x，还原时求一遍前缀和
互逆
差分求前缀和还原数组，前缀和做差分还原原数组
旋转数组处理
旋转后的有序数组仍大半有序：二分时先判断哪半边是有序的。
判有序半边
左端 ≤ 中点则左半有序，否则右半有序
目标落位
看 target 是否落在有序半边的区间内
旋转点
最小值即旋转点，与右端比较即可二分定位
本节要点
- ✓对撞夹逼，快慢追击，原地 O(1)
- ✓右扩左缩，窗口状态 O(1) 维护
- ✓前缀和查区间，差分改区间
- ✓旋转数组：先定有序半边再二分
延伸主题：刷无重复最长子串手写区间和查询
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1滑动窗口为什么是 O(n)？内层 while 不算嵌套吗？
参考答案左右指针各自最多走 n 步，内层 while 的总执行量摊给左指针的全程，不与右指针相乘。总移动次数约 2n，故 O(n)——这是双指针类题目的通用论证。
2什么时候用前缀和，什么时候用滑动窗口？
参考答案窗口要求连续且条件单调（扩一个，好坏方向一致）；区间和是精确查询，前缀和直接作答。窗口求最值长度，前缀和解计数与定位问题。
3旋转数组二分为什么容易写错？
参考答案坑在边界：中点与 left 还是 right 比、等号算不算有序、收缩时 mid±1。记住「先判哪半有序，再看 target 在不在里面」，写完用小样例走一遍边界。