删除有序数组中的重复项

怎样从“给定升序数组 [1,1,2,3,3],原地去重,使每个元素只出现一次,返回新长度。”推导出 数组写游标 · 快慢指针，并证明每次状态变化都不会漏掉答案？

中心结论：数组有序,重复值必相邻;slow 指向结果区末尾,fast 扫描,遇到与结果区末尾不同的新值才前移 slow 并写入。

给定一个有序数组 nums，对数组中的元素进行去重，使得原数组中的每个元素只有一个。最后返回去重以后数组的长度值。

在本站主例中，给定升序数组 [1,1,2,3,3],原地去重,使每个元素只出现一次,返回新长度。

算法最终需要得到或观察：数组前 slow+1 个元素是去重结果,返回值为 3。

为每个位置复制或删除元素，会产生重复搬运；先建立正确基线，再把有效元素原地覆盖到写指针位置。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“读写游标”，明确答案需要观察什么。
2. 2状态只维护 结果区末尾 slow、扫描指针 fast、唯一值个数。
3. 3转移每一步按照 数组有序,重复值必相邻;slow 指向结果区末尾,fast 扫描,遇到与结果区末尾不同的新值才前移 slow 并写入。
4. 4收尾读取 数组前 slow+1 个元素是去重结果,返回值为 3。，并复核边界与复杂度。

读指针负责发现信息，写指针只在答案确定时落笔。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：结果区末尾 slow、扫描指针 fast、唯一值个数。

这道题和第 27 题很像。这道题和第 283 题，第 27 题基本一致，283 题是删除 0，27 题是删除指定元素，这一题是删除重复元素，实质是一样的。

这里数组的删除并不是真的删除，只是将删除的元素移动到数组后面的空间内，然后返回数组实际剩余的元素个数，OJ 最终判断题目的时候会读取数组剩余个数的元素进行输出。

数组有序,重复值必相邻;slow 指向结果区末尾,fast 扫描,遇到与结果区末尾不同的新值才前移 slow 并写入。

执行过程中持续维护：结果区末尾 slow、扫描指针 fast、唯一值个数。

正确性依赖以下不变量：下标区间 [0, slow] 严格递增,无重复。；有序性保证重复值一定相邻,只需和结果区末尾比较。

面试时可以压缩为：因为数组有序、重复必相邻,我用快慢指针:slow 指向结果区末尾,fast 扫描,只有 a[fast] 与 a[slow] 不同才 slow++ 并写入;返回 slow+1。

落到当前题，执行机制可以压缩为：数组有序,重复值必相邻;slow 指向结果区末尾,fast 扫描,遇到与结果区末尾不同的新值才前移 slow 并写入。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入给定升序数组 [1,1,2,3,3],原地去重,使每个元素只出现一次,返回新长度。 因为：数组有序,重复值必相邻;slow 指向结果区末尾,fast 扫描,遇到与结果区末尾不同的新值才前移 slow 并写入。
2. 2首元素直接入结果有序数组里第一个元素不可能和前面重复,直接作为结果起点。 因为：去重只需保证「结果区相邻不同」,首元素无前驱,天然合法。
3. 3丢弃重复 11 不进入结果,slow 不动,fast 继续向前。 因为：只有 fast 单独前移,才能让 slow 这个写位「等着」下一个该保留的值。
4. 4检查 a[fast]=2读取 a[fast]=2,与判定规则比较。 因为：2 与已确定区末尾不同,应当进入结果区。
5. 5保留新值 2把 2 写到 slow 处,slow 前移一格。 因为：slow 永远指向「下一个待写入位置」,所以写完必须前移,否则会覆盖结果。
6. 6保留新值 3把 3 写到 slow 处,slow 前移一格。 因为：slow 永远指向「下一个待写入位置」,所以写完必须前移,否则会覆盖结果。
7. 7丢弃重复 33 不进入结果,slow 不动,fast 继续向前。 因为：只有 fast 单独前移,才能让 slow 这个写位「等着」下一个该保留的值。
8. 8收尾与复杂度数组前 slow+1 个元素是去重结果,返回值为 3。 因为：时间 O(n) · 空间 O(1)。数组有序,重复值必相邻;slow 指向结果区末尾,fast 扫描,遇到与结果区末尾不同的新值才前移 slow 并写入。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一
func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	last, finder := 0, 0
	for last < len(nums)-1 {
		for nums[finder] == nums[last] {
			finder++
			if finder == len(nums) {
				return last + 1
			}
		}
		nums[last+1] = nums[finder]
		last++
	}
	return last + 1
}

// 解法二
func removeDuplicates1(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	length := len(nums)
	lastNum := nums[length-1]
	i := 0
	for i = 0; i < length-1; i++ {
		if nums[i] == lastNum {
			break
		}
		if nums[i+1] == nums[i] {
			removeElement1(nums, i+1, nums[i])
			// fmt.Printf("此时 num = %v length = %v\n", nums, length)
		}
	}
	return i + 1
}

func removeElement1(nums []int, start, val int) int {
	if len(nums) == 0 {
		return 0
	}
	j := start
	for i := start; i < len(nums); i++ {
		if nums[i] != val {
			if i != j {
				nums[i], nums[j] = nums[j], nums[i]
				j++
			} else {
				j++
			}
		}
	}
	return j
}

func main() {
    // 1. 主例
    //    输入：mode="dedupe", array=[1,1,2,3,3]
    //    期望：数组前 slow+1 个元素是去重结果,返回值为 3。
    //
    // 2. 失败 / 未命中
    //    检查：误以为要和「前一个原始元素」比较,实际要和「结果区末尾」比较。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC27 移除元素；LC283 移动零
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意给定升序数组 [1,1,2,3,3],原地去重,使每个元素只出现一次,返回新长度。
2. 2重复为每个位置复制或删除元素，会产生重复搬运；先建立正确基线，再把有效元素原地覆盖到写指针位置。
3. 3优化数组有序,重复值必相邻;slow 指向结果区末尾,fast 扫描,遇到与结果区末尾不同的新值才前移 slow 并写入。
4. 4证明下标区间 [0, slow] 严格递增,无重复。；有序性保证重复值一定相邻,只需和结果区末尾比较。
5. 5复杂度时间 O(n)，空间 O(1)