右指針不斷移動獲取解，左指針不斷移動縮小解范圍

左指針的意義非常重要，相當于一個標兵，不斷與這個標兵進行比較，如果符合要求，這左指針進行移動，并進行操作，如果不符合要求，則左指針不動，右指針接著尋找符合要求的值。

刪除有序數組中的重復項

給你一個 非嚴格遞增排列 的數組 nums ，請你 原地 刪除重復出現的元素，使每個元素 只出現一次 ，返回刪除后數組的新長度。元素的 相對順序 應該保持 一致 。然后返回 nums 中唯一元素的個數。
輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]

暴力解法

一種非常簡單的辦法就是創建一個新的數組，每次添加元素的時候判斷是否已經添加過了

class Solution:def removeDuplicates(self, nums: List[int]) -> int:res = []for v in nums:if v in res:continueres.append(v)return res

但是要求我們原地刪除重復的數組，不能創建新的數組。因為數組是有序的，相同的元素已經排在了一起，如果前后兩個元素不同，那么我們就找到了一個新的元素。

滑動窗口

我么定義兩個指針l和r，右指針不斷往后遍歷找到與左指針不同的元素，找到以后左指針也往后走一步，然后進行交換

1. 初始化左指針和右指針

0	0	0	0	1	1	2	3
l,r

2. 右指針不斷遍歷找到不同的元素

0	0	0	0	1	1	2	3
l				r

3. 左指針移動一位，準備放入下一個不同元素

0	0	0	0	1	1	2	3
	l			r

4. 把當前不同的元素放到前面

0	1	0	0	1	1	2	3
	l			r

5. 重復之前的邏輯

右指針不斷移動找下一個不同的元素

0	1	0	0	1	1	2	3
	l					r

找到后左指針移動并填充

0	1	2	0	1	1	2	3
		l				r

右指針不斷移動找下一個不同的元素

0	1	0	0	1	1	2	3
	l						r

找到后左指針移動并填充

0	1	2	3	1	1	2	3
			l				r

6.右指針到底末端結束

class Solution:def removeDuplicates(self, nums: List[int]) -> int:l = 0for r in range(len(nums)):if nums[l] != nums[r]:l += 1nums[l] = nums[r]return l+1

在這個問題中，我們可以破壞數組，所以可以直接將后面的元素覆蓋到前面去

刪除有序數組中的重復項 II

給你一個有序數組 nums ，請你 原地 刪除重復出現的元素，使得出現次數超過兩次的元素只出現兩次 ，返回刪除后數組的新長度。
不要使用額外的數組空間，你必須在 原地 修改輸入數組 并在使用 O(1) 額外空間的條件下完成。

暴力解法

我們定義一個數組，不斷添加元素，如果與這個數組尾端不同，則直接添加進來，如果與尾端相同，我們則判斷添加的次數，超過2之后不在添加

class Solution:def removeDuplicates(self, nums: List[int]) -> int:tmp = []k = 1for i in range(len(nums)):# 如果為空則直接添加# 如果與末端元素不同也直接添加if not tmp or tmp[-1] != nums[i]:tmp.append(nums[i])k = 1# 如果與末端元素相同，則記錄添加的次數k += 1# 小于2次則接著添加if k <= 2:tmp.append(nums[i])return tmp           

一個小小的優化是，其實我們不需要記錄重復的次數，由于末端我們只會2個相同的元素，因此只需要比較tmp[-2]是否相同即可

	temp[-3]	temp[-2]	temp[-1]	nums[i]
前兩個相同	x	x	y	nums[i]!=tmpe[-2]，說明中間只有一個y，可以直接添加
后兩個相同	x	y	y	如果nums[i]==temp[-2]，說明中間已經有一個y了，不能再添加了
全都不同	x	z	y	nums[i]!=tmpe[-2]，說明中間只有一個y，可以直接添加

class Solution:def removeDuplicates(self, nums: List[int]) -> int:if len(nums) <= 2:return numstmp = [nums[0],nums[1]]for i in range(2, len(nums)):# 如果為空則直接添加# 如果nums[i] != tmp[-2]說明末端元素只有一個，無腦添加if not tmp or tmp[-2] != nums[i]:tmp.append(nums[i])return tmp    

滑動窗口

數組是有序的，因此所有相同的元素肯定都是在一起出現的，同時要求一個元素最多出現兩次，一個簡單的想法就是
右指針不斷移動，直到找到與左指針不同的元素，我們要把這個不同元素保留下來，即直接放到前面去（當前左指針后面）

0	0	0	0	1	1	1	2	3
l				r

放到前面去

0	1	0	0	1	1	1	2	3
	l			r

由于重復元素需要保留2個，左指針需要再移動一位存放元素

0	1	0	0	1	1	1	2	3
		l			r

把重復的第2個值保留到前面

0	1	1	0	1	1	1	2	3
		l			r

當前這個元素已經滿足要求了（不超過2個），右指針接著往后找下個不同的元素

0	1	1	0	1	1	1	2	3
		l					r

我們需要記錄當前元素已經找到幾個相同的了，如果小于等于2，那么左指針都需要跟著走，如果大于2了，左指針就不要動了，一直等找到下一個不同的元素

理清思路

好好理一下思路

1. 右指針不斷后移找到不同的元素
2. 定義一個變量，記錄當前的元素重復的次數
3. 如果小于等于k，那么左指針移動，并將這個元素保留過來
4. 如果重復次數超過了k，左指針不動，一直找到下一個重復元素，k重新賦值為1

class Solution:def removeDuplicates(self, nums: List[int]) -> int:if not nums:  # 處理空數組return 0l = 0k = 1  # nums[l] 初始出現1次# r從1開始，因為0位置已被l標記for r in range(1, len(nums)):if nums[l] == nums[r]:k += 1# 出現次數<=2時，擴展有效數組if k <= 2:l += 1nums[l] = nums[r]  # 這里漏了賦值，需要補充else:# 遇到新元素，重置計數并擴展有效數組k = 1l += 1nums[l] = nums[r]return l + 1

滑動窗口優化

因為數組是有序的，重復元素會連續排列。假設有效數組的最后兩個元素是nums[l-2]和nums[l-1]（當l >= 2時），此時：

• 如果num == nums[l-2]，說明nums[l-2]、nums[l-1]、num三者相等（因為數組有序，中間的nums[l-1]必然也等于num），加入num就會導致該元素出現 3 次，不符合要求。
• 如果num != nums[l-2]，說明即使num和nums[l-1]相等（最多出現 2 次），也不會超過限制，因此可以加入有效數組。

from typing import Listclass Solution:def removeDuplicates(self, nums: List[int]) -> int:l = 0  # 慢指針：指向有效數組的末尾for num in nums:# 核心判斷：# 1. 有效數組長度不足2時，直接加入（前兩個元素一定有效）# 2. 超過2個元素時，若當前元素與有效數組倒數第二個不同，說明可加入（避免3次重復）if l < 2 or num != nums[l-2]:nums[l] = numl += 1return l