What is the two-pointer technique in this problem?

The two-pointer technique involves using two indices to traverse the array: one for scanning and the other for tracking the position to place unique elements.

How does the solution handle edge cases?

The solution accounts for edge cases such as arrays with no duplicates or arrays where all elements are the same by ensuring the two-pointer logic doesn't fail or result in errors.

Why is it important to modify the array in-place?

Modifying the array in-place ensures that the space complexity remains O(1) and the result is stored directly in the given array, as required by the problem constraints.

Can the array length vary? How does this affect the solution?

Yes, the array length can vary. The solution is designed to handle arrays up to 30,000 elements, making it efficient and scalable for large inputs.

What are common mistakes when implementing the two-pointer technique?

Common mistakes include incorrectly managing the pointers, not handling the edge cases properly, or failing to ensure the in-place modification is achieved without additional memory usage.

#80

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

删除有序数组中的重复项 II

给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。说明：为什么返回数值是整数，但输出的答案是数组呢？请注意，输入数组是…

数组双指针

题目描述

给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 10⁴
-10⁴ <= nums[i] <= 10⁴
nums 已按升序排列

lightbulb

解题思路

方法一：一次遍历

我们用一个变量 $k$ 记录当前已经处理好的数组的长度，初始时 $k=0$ ，表示空数组。

然后我们从左到右遍历数组，对于遍历到的每个元素 $x$ ，如果 $k \lt 2$ 或者 $x \neq nums[k-2]$ ，我们就将 $x$ 放到 $nums[k]$ 的位置，然后 $k$ 自增 $1$ 。否则， $x$ 与 $nums[k-2]$ 相同，我们直接跳过这个元素。继续遍历，直到遍历完整个数组。

这样，当遍历结束时， $nums$ 中前 $k$ 个元素就是我们要求的答案，且 $k$ 就是答案的长度。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组的长度。

补充：

原问题要求最多相同的数字最多出现 $2$ 次，我们可以扩展至相同的数字最多保留 $k$ 个。

由于相同的数字最多保留 $k$ 个，那么原数组的前 $k$ 个元素我们可以直接保留；
对于后面的数字，能够保留的前提是：当前数字 $x$ 与前面已保留的数字的倒数第 $k$ 个元素比较，不同则保留，相同则跳过。

相似题目：

26. 删除有序数组中的重复项

1

2

3

4

5

6

7

8

9

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0
        for x in nums:
            if k < 2 or x != nums[k - 2]:
                nums[k] = x
                k += 1
        return k

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understand the candidate's ability to handle array manipulation in-place.
question_mark
Look for clarity in using the two-pointer approach and maintaining order without extra space.
question_mark
Check if the candidate is mindful of edge cases, such as handling arrays with no duplicates or all duplicates.

warning

常见陷阱

外企场景

error
Incorrectly handling the array's length, returning an incorrect value for k.
error
Not managing the two-pointer correctly, resulting in array elements being overwritten prematurely.
error
Misunderstanding that the elements beyond the first k positions do not need to be handled.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing elements to appear more than twice, which requires adjusting the comparison logic.
arrow_right_alt
Modifying the input array to return k but allowing the rest of the array to remain unchanged.
arrow_right_alt
Solving the problem using a different technique, such as a hash set or direct indexing.

help

常见问题

外企场景

继续练习

#75 颜色分类 #88 合并两个有序数组 #42 接雨水