LeetCode 26. Remove Duplicates from Sorted Array 题解题目描述给你一个升序排列的数组nums请你原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。不要使用额外的数组空间你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。示例 1输入nums [1,1,2] 输出2, nums [1,2,_] 解释函数应该返回新的长度 2 并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。示例 2输入nums [0,0,1,1,1,2,2,3,3,4] 输出5, nums [0,1,2,3,4] 解释函数应该返回新的长度 5 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。解题思路方法双指针思路使用两个指针一个慢指针slow指向当前已处理的无重复元素的末尾一个快指针fast遍历整个数组初始时slow指向 0fast指向 1遍历数组如果nums[fast]不等于nums[slow]说明找到一个新的无重复元素将slow右移一位然后将nums[fast]赋值给nums[slow]无论是否找到新元素fast都右移一位遍历结束后slow 1就是删除重复元素后的数组长度复杂度分析时间复杂度O(n)其中 n 是数组的长度。只需要遍历数组一次。空间复杂度O(1)只需要常数级的额外空间。代码实现方法双指针class Solution: def removeDuplicates(self, nums: List[int]) - int: n len(nums) if n 0: return 0 # 慢指针指向当前已处理的无重复元素的末尾 slow 0 # 快指针遍历整个数组 for fast in range(1, n): # 如果找到一个新的无重复元素 if nums[fast] ! nums[slow]: # 将 slow 右移一位 slow 1 # 将新元素赋值给 nums[slow] nums[slow] nums[fast] # slow 1 就是删除重复元素后的数组长度 return slow 1测试用例测试用例 1输入nums [1,1,2]输出2测试用例 2输入nums [0,0,1,1,1,2,2,3,3,4]输出5测试用例 3输入nums []输出0测试用例 4输入nums [1]输出1总结本题是双指针的经典应用问题主要考察对双指针技巧的理解和使用。通过使用慢指针和快指针我们可以在原地删除排序数组中的重复元素。双指针的核心思想是慢指针指向当前已处理的无重复元素的末尾快指针遍历整个数组当找到新的无重复元素时将其移动到慢指针的位置然后慢指针右移。这种方法不仅适用于删除排序数组中的重复元素还可以应用于许多其他需要原地修改数组的问题例如移除元素、移动零等。掌握双指针的使用对于解决这类问题非常重要。