1. //给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。 
  2. //
  3. // 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 
  4. //
  5. // 
  6. //
  7. // 说明： 
  8. //
  9. // 为什么返回数值是整数，但输出的答案是数组呢？ 
  10. //
  11. // 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 
  12. //
  13. // 你可以想象内部操作如下: 
  14. //
  15. // 
  16. //// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
  17. //int len = removeDuplicates(nums);
  18. //
  19. //// 在函数里修改输入数组对于调用者是可见的。
  20. //// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
  21. //for (int i = 0; i < len; i++) {
  22. //    print(nums[i]);
  23. //}
  24. // 
  25. //
  26. // 
  27. //
  28. // 示例 1： 
  29. //
  30. // 
  31. //输入：nums = [1,1,1,2,2,3]
  32. //输出：5, nums = [1,1,2,2,3]
  33. //解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
  34. // 
  35. //
  36. // 示例 2： 
  37. //
  38. // 
  39. //输入：nums = [0,0,1,1,1,1,2,3,3]
  40. //输出：7, nums = [0,0,1,1,2,3,3]
  41. //解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的
  42. //元素。
  43. // 
  44. //
  45. // 
  46. //
  47. // 提示： 
  48. //
  49. // 
  50. // 1 <= nums.length <= 3 * 104 
  51. // -104 <= nums[i] <= 104 
  52. // nums 已按升序排列 
  53. // 
  54. // Related Topics 数组 双指针 
  55. // 👍 432 👎 0

移除超过两个相同的项。
因为题目给出的数组是有序的，所以必然相同的元素是相邻的。

双指针

因此可以使用双指针将相同的元素框出来，再移动到数组前列。
如果框出来的元素超过或等于两个，就只移动两个过去，如果不足两个，就只移动一个。

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         int n = nums.length;
  4.         // 标记当前数组前面已经放了多少个元素
  5.         int index = 0;
  6.         int i = 0;
  7.         while (i < n) {
  8.             // 使用[left, right)去框选相同的元素
  9.             int left = i;
  10.             int right = i + 1;
  11.             // 如果left == right,right就右移
  12.             while (right < n && nums[right] == nums[left]) {
  13.                 right ++;
  14.             }
  16.             // 如果相同的元素数量大于等于2，只移动两个过去
  17.             if (right - left > 1) {
  18.                 // 有需要删除的数据
  19.                 nums[index] = nums[left];
  20.                 nums[index + 1] = nums[left];
  21.                 index += 2;
  22.             }else {
  23.                 // 否则说明只有一个元素，只移动一个过去
  24.                 nums[index] = nums[left];
  25.                 index += 1;
  27.             }
  28.             // 此时i已经判断完[left, right - 1]
  29.             i = right;
  30.         }
  31.         return index;
  32.     }
  33. }

相同元素计数

因为只要求重复，所以我们只对前两个或者不重复的数字感兴趣，对于什么时候结束重复兴趣不大。
所以可以只记录当前i指示的数字重复了多少次，当小于等于2的时候才移动到数组头。大于2的时候就直接不感兴趣了。

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         int i = 1;
  4.         int count = 1;
  5.         for (int j = 1; j < nums.length; j++) {
  6.             // 如果当前数和前面相等的话，计数+1
  7.             if (nums[j] == nums[j - 1]) {
  8.                 count ++;
  9.             }else {
  10.                 // 如果不相等，说明换成了新的数字，计数回到1
  11.                 count = 1;
  12.             }
  13.             // 如果计数小于等于2，这时移动到数组前部，如果超过2就直接抛弃
  14.             if (count <= 2) {
  15.                 nums[i] = nums[j];
  16.                 i ++;
  17.             }
  18.         }
  19.         return i;
  20.     }
  22. }

直接移动

如果数组i位置的数相同超过2个，那么到达i的时候 nums[i - 2] == nums[i]
因此可以使用这个特点，不再计数，直接判断是否当前数字已经满了。

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         int i = 0;
  4.         for (int num : nums) {
  5.             // i < 2是因为，无论数组长什么样，前两个数字肯定是符合要求的
  6.             // i指示的是当前应该放数字的位置。 如果向前两个位置和当前数字相同，意味着相同数字已经足够了，可以直接抛弃
  7.             if (i < 2 || nums[i - 2] < num) {
  8.                 nums[i] = num;
  9.                 i ++;
  10.             }
  11.         }
  12.         return i;
  13.     }
  14. }