快慢指针经典题目：删除有序数组中的重复项 | IT宅-帅旋的专业知识分享

题目：26. 删除有序数组中的重复项^[1]

如果您已经有思路了，或者是N刷了，可以先自己写一遍。

题目分析

这也是一个比较常见的问题，设计目标是就地（不使用额外的数组空间）删除排序数组中的重复元素，使得每个元素只出现一次，并返回修改后数组的新长度。

我们可以使用快慢针技术。这个技术的核心思想是使用两个指针在一次遍历中完成任务：一个慢指针 i，一个快指针 j。

解题思路

快指针用于探索数组前面，而慢指针标记了无重复数组的当前结束位置。

当我们遇到一个新的元素（即与慢指针指向的元素不同的元素），我们就将它复制到慢指针的下一个位置，然后两个指针都前进一步。

如果快指针指向的元素与慢指针指向的元素相同，我们只将快指针前进一步。

这样，当快指针遍历完整个数组时，从数组的开始到慢指针的位置就是无重复元素的数组，且我们没有使用额外的空间。

Java解法

下面是使用Java语言的解法：

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1; // 返回新的数组长度
    }
}

这种方法的优点是空间复杂度低（O(1)），因为它不需要额外的存储空间来存储结果。

这个技巧在处理有序数组或链表中的问题时非常有用，能够有效地减少不必要的数据移动或复制，从而提高算法的效率。

References

---

1. 26. 删除有序数组中的重复项. Retrieved from https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ ↩︎