给定一个包含红色、白色和蓝色，一共 n 个元素的数组，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
示例 3：
输入：nums = [0]
输出：[0]
示例 4：
输入：nums = [1]
输出：[1]
提示：
n == nums.length1 <= n <= 300-
nums[i]为0、1或2
进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
通过次数269,325提交次数451,982
一解
使用三指针：
- p0：从开头指向结尾。
- p2：从结尾指向开头。
- i：当前位置，若 nums[i] 为 0 ，将 i 位置的元素与 p0 位置的元素进行交换。若 nums[i] 为 2 ，将 i 位置的元素与 p2 位置的元素进行交换。
注意：p2 位置的元素可能为 2，当 i 位置元素为 2 时，此时 i 位置元素不应该与 p2 位置元素进行交换，应该循环判断 nums[i] == 2。而 p0 位置元素不可能为 0，因为 i 在 p0 前，若 i 位置元素为 0 ，会与 p0 位置元素进行交换，然后 p0 += 1，相当于 i 已经为 p0 踩坑了，p0 的路很顺。
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
p1, p2, i = 0, n - 1, 0
while i <= p2:
while i <= p2 and nums[i] == 2:
nums[i], nums[p2] = nums[p2], nums[i]
p2 -= 1
if nums[i] == 0:
nums[i], nums[p1] = nums[p1], nums[i]
p1 += 1
i += 1
return nums
- 时间复杂度 O(n)：n 为 nums 长度。
- 空间复杂度 O(1)。