各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 72 天。今天力扣上的每日一题是「80. 删除有序数组中的重复项 II」。

解题思路

题目大意：一个有序数组中，让每个数字最多出现两次，返回一个 n ，使得数组的前 n 个元素就是结果。需要在输入数组上原地修改。

今天这个题目是 26. 删除有序数组中的重复项 的进阶，可以先做一下 26 题。

注意是原地修改，那么肯定就需要一个指针指向当前即将放置元素的位置，需要另外一个指针向后遍历所有元素，所以「双指针」解法就呼之欲出了。如果能想到双指针解法，后面的分析也就顺理成章。

  • 慢指针 slow: 指向当前即将放置元素的位置；则 slow - 1 是刚才已经放置了元素的位置。
    - 快指针 fast: 向后遍历所有元素；

因为最多允许两个重复元素，并且 slow - 2 位置是上上次放置了元素的位置，所以让 nums[fast] 跟 nums[slow - 2] 进行比较。每次都是只允许最多两个元素出现重复，这两个元素的位置在 slow - 1 和 slow - 2.

请看下面的动图展示，一图胜千言。图中红色表示已经放置了正确元素的位置，绿色表示当前元素被修改了。

代码

代码挺简洁的。

  1. class Solution(object):
  2.     def removeDuplicates(self, nums):
  3.         slow = 0
  4.         for fast in range(len(nums)):
  5.             if slow < 2 or nums[fast] != nums[slow - 2]:
  6.                 nums[slow] = nums[fast]
  7.                 slow += 1
  8.         return slow
  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(1)$

刷题心得

今天的题目乍一看很难，明白了两个指针的含义之后，思路就会简单很多。这就说明在刷题的过程中，务必清晰理解记忆每个变量、每个函数的定义，这样做题才不会迷茫。如果看不懂别人的题解，也首先要明白别人的题解中定义的各个变量的含义，这是理解的基础。

参考资料：
力扣官方题解
Grandyang
负雪明烛

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！