← 返回笔记
C++ / 算法待回顾

双指针不是两个下标:从有序数组去重理解状态不变量

以原地删除重复元素为例,记录快慢指针各自表达的状态、循环不变量,以及为什么只记代码模板很容易在变体题中失效。

C++Two PointersInvariantvector

双指针不是两个下标

双指针真正需要掌握的不是“定义两个 int”,而是两个位置分别代表什么。

状态定义

  • fast:正在检查的候选元素。
  • slow:已经确认有效区间的最后一个位置。
  • [0, slow]:始终保持去重后的正确结果。

典型实现

int removeDuplicates(std::vector<int>& nums) {
  if (nums.empty()) return 0;

  int slow = 0;
  for (int fast = 1; fast < nums.size(); ++fast) {
    if (nums[fast] != nums[slow]) {
      nums[++slow] = nums[fast];
    }
  }
  return slow + 1;
}

回顾重点

判断条件比较的是候选值与有效区间末尾,而不是简单比较相邻循环变量。遇到“最多保留两次”“移动零”等变体时,应先重新写出有效区间的不变量,再决定指针如何移动。