难度: Medium
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]
提示：
n == nums.length1 <= n <= 300nums[i] 为 0、1 或 2进阶：
运行时间: 52 ms
内存: 15 MB
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) < 2:
return
# [0, p0) = 0
# [p0, i) = 1
# (p2, len-1] = 2
p0 = 0
p2 = len(nums)-1
i = 0
while i <= p2:
if nums[i] == 0:
nums[i] = 0
p0 += 1
i += 1
elif nums[i] == 1:
i += 1
else:
nums[i], nums[p2] = nums[p2], nums[i]
p2 -= 1
这个题解使用了双指针的方法，通过维护三个指针p0, p2和i来将数组分成三个部分：[0, p0)表示已经排好序的0，(p2, len-1]表示已经排好序的2，[p0, i)表示已经扫描过的1。初始时p0和i都指向数组开头，p2指向数组末尾。然后用i来遍历数组，如果遇到0，就与p0位置交换，并将p0和i都右移一位；如果遇到2，就与p2位置交换，并将p2左移一位；如果遇到1，则直接将i右移一位。这样交换和移动指针直到i>p2，最后数组就按照0,1,2的顺序排好序了。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) < 2:
return
# [0, p0) = 0
# [p0, i) = 1
# (p2, len-1] = 2
p0 = 0
p2 = len(nums)-1
i = 0
while i <= p2:
if nums[i] == 0:
nums[p0], nums[i] = nums[i], nums[p0] # 遇到0，交换到p0位置
p0 += 1
i += 1
elif nums[i] == 1:
i += 1 # 遇到1，不做交换，指针后移
else:
nums[i], nums[p2] = nums[p2], nums[i] # 遇到2，交换到p2位置
p2 -= 1 # p2 左移，i不动，因为交换过来的元素还没处理过
在算法中，当i指向的元素为2时，这个元素需要和p2指向的位置进行交换，以便把2移动到数组的右侧。交换后，p2指针左移是为了更新未排序的2的边界，减小未处理的区域。而i指针不移动是因为交换到i位置的元素是从p2位置移过来的，这个新的元素还未被检查，所以i需要保持在当前位置进行下一轮判断，以确保所有元素都能正确处理。
如果数组长度小于2，即数组为空或只有一个元素时，数组已经天然有序，不需要进行任何排序操作。在这种情况下，直接返回是为了避免不必要的计算和操作，因为单个元素或空数组不需要排序。
算法中有一个重要的控制条件：只有当i小于或等于p2时，循环才会继续。每次遇到2并进行交换后，p2都会向左移动一位，而i保持不动，这意味着每次处理2都会减小未检查的区域。即使交换后i位置上仍然是2，i不会立即右移，而是等待下一轮循环再进行处理，直至i超过p2，此时所有的2都已经移到数组右侧，循环结束。这保证了算法不会进入无限循环。
在算法执行过程中，所有遇到的0都被移到数组的最左边，更新p0指针的位置，而所有遇到的2都移到数组的最右边，更新p2指针的位置。由于i从左至右遍历，遇到1时仅i指针向右移动，不进行任何交换。这确保了在p0和p2之间的区域（即i遍历过的区域）最终只会留下1，因为所有的0和2都已被移到它们相应的位置。扫描完成时，p0到p2的区间自然形成了只包含1的区域，从而满足题目要求。