双指针

0 Two Pointers Basic 双指针是什么？ 用两个指针（下标）在数组/链表上协同移动，通过缩小搜索范围来降低复杂度 两大类型： 类型 特征 典型题 对撞指针 一头一尾，向中间逼近 盛水容器、三数之和 快慢指针 同向移动，速度不同 移动零、链表环检测 使用双指针的条件： 通常数组有序（或者问题本身有单调性） 如果无序，往往需要先排序 双指针能降低复杂度原因：利用了单调性，使得指针不需要回退，将 O(n²) 降到 O(n) 1 快慢指针（数组原地操作） 1.1 移动零 | Easy 题目： 将数组中所有 0 移到末尾，保持非零元素的相对顺序。原地操作 [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0] 思路分析： 用快慢指针，left指向当前最左边的0的位置，i找非0，然后swap left：慢指针，始终指向下一个非零元素该放的位置 i： 快指针，遍历数组寻找非零元素 left左边都是已经处理好的非零元素，每找到一个非零元素，就交换到left位置，然后left右移 走一遍[0, 1, 0, 3, 12]: i=0, nums[0]=0 → 是0，跳过 zero=0, [0, 1, 0, 3, 12] i=1, nums[1]=1 → 非0，和zero交换 zero=1, [1, 0, 0, 3, 12] i=2, nums[2]=0 → 是0，跳过 zero=1, [1, 0, 0, 3, 12] i=3, nums[3]=3 → 非0，和zero交换 zero=2, [1, 3, 0, 0, 12] i=4, nums[4]=12 → 非0，和zero交换 zero=3, [1, 3, 12, 0, 0] 踩坑记录：搞清楚两个指针的含义以及交换条件 ...