class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
#双指针的思想就是：只管0和2，不管1.如果遇到0就把它放在列表头，如果遇到2就把它放在列表尾把，如果是1直接跳过
l,index,r = 0,0,len(nums)-1
while index<=r:
if nums[index]==0:
nums[index],nums[l] = nums[l],nums[index]
index+=1
l+=1
elif nums[index]==1:
index+=1
else:
nums[index],nums[r] = nums[r],nums[index]
r-=1
#需要用空间复杂度的话，那就把0，1，2的个数统计出来，然后生成新的数组
dic = {0:0,1:0,2:0}
for i in nums:
dic[i]+=1
nums.clear()
for k,v in dic.items():
nums.extend([k]*v)
题目不让使用任何内置函数而且是最好原地操作，意味着空间复杂度是O(1)使用空间
使用hash表统计出来每个颜色出现的个数，然后按顺序进行拼接原地操作
使用双指针法进行操作，因为只有三种颜色，所有双指针进行操作的时候，把0放在表头，2放在表尾，这样一次遍历之后自然1就在中间了
总结：本题目就考察双指针法，但是需要用到一个index变量而不是传统的双指针，是左右指针。如果是0，那交换当前位置和表头位置，如果是1直接跳过，如果是2那么就交换表尾的元素，并且不需要进行index+1，原因在于交换过来的元素可能是1而不是0，所以还需要对交换过后的元素进行判断。之前做题没有遇到过类似的双指针问题。往往需要原地操作的都需要双指针去解决这个问题。
