滑动窗口

核心：使用快慢指针
滑动窗口算法的思路是这样：

1. 我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
2. 我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3. 此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4. 重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
模版：

"""给定待查串s和目标串t"""
need, window = {}, {}
for c in t:
    记录need     # 视具体问题而定
left, right = 0, 0
valid = 0
while right < len(s):        # 窗口右边界不断扩大，本质是搜索问题的可能解
    c = s[right]      # 即将加入到窗口中的字符
    right += 1
    更新窗口中的数据
    while 满足窗口收缩条件：  # 窗口的左边界收缩，本质是优化可行解
        记录或返回结果
        d = s[left]   # 即将从窗口中删除的字符
        left += 1
        更新窗口中的数据
return 结果

最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”

class Solution:
    def minWindow(self, s, t):
        # 只要保证窗口(队列)字符串含有t中字符的个数大于等于t里相应元素个数
        # 这种方法key不存在不会报错
        from collections import defaultdict
        lookup = defaultdict(int)
        for c in t:
            lookup[c] += 1
        right = 0
        left = 0
        min_len = float("inf") # 正无穷
        counter = len(t)
        res = ""
        # right指针小于len(s)的情况下，用counter计数器记录left到right之间的s的子串包含t的数量
        while right < len(s):
            if lookup[s[right]] > 0:
                counter -= 1
            lookup[s[right]] -= 1
            right += 1
            # 如果s在left到right之间的子串完全包含t,即满足counter = 0 时，通过不断缩小left来缩小窗口
            while counter == 0:
                # 记录最小值和res
                if min_len > right - left:
                    min_len = right - left
                    res = s[left:right]
                # left向右移动的过程，如果匹配字母被去掉，counter要更新
                if lookup[s[left]] == 0:
                    counter += 1
                lookup[s[left]] += 1
                left += 1
        return res

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        # 方法一：快慢指针+散列表，cur先走，遇到重复的就移动pre到第一个重复的cur位置
        if len(s) == 0:
            return 0
        dicts = {}
        pre = 0
        cur = 0
        max_p = 0
        while cur < len(s):
            if s[cur] in dicts:
                # 将pre移动到cur的位置
                pre = max(pre, dicts[s[cur]] + 1)
            dicts[s[cur]] = cur
            max_p = max(max_p, cur-pre + 1)
            cur += 1
        return max_p

判断是否是子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。
s = “abc”, t = “ahbgdc”
返回 true.
s = “axc”, t = “ahbgdc”
返回 false.

class Solution(object):
    def isSubsequence(self, s, t):    
        cur = 0
        pre = 0
        while cur < len(s) and pre < len(t):
            if s[cur] == t[pre]:
                cur += 1
                pre += 1
            else:
                pre += 1
        if cur == len(s):
            return True
        else:
            return False

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
输入：nums = []
输出：[]

# 固定一个指针，然后创建另外两个指针，一个放前面，一个放后面，
class Solution(object):
    def threeSum(self, nums):
        # 方法一：三个指针，固定一个，另外两个滑动窗口，去重放里面
        if not nums or len(nums) < 3:
            return []
        nums.sort()
        res = []
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if nums[i] + nums[left] + nums[right] == 0:
                    res.append([nums[i], nums[left], nums[right]])
                    # 去重
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                else:
                    left += 1
        return res
        # 方法二：三个指针，感觉这种更好理解，固定一个，另外两个滑动窗口，去重放外面
        if not nums or len(nums) < 3:
            return []
        lists = []
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if nums[i] + nums[left] + nums[right] == 0:
                    lists.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                elif nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                else:
                    left += 1
        # 去重
        res = []
        for j in lists:
            if j not in res:
                res.append(j)
        return res

四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
输入：nums = [], target = 0
输出：[]

class Solution(object):
    def fourSum(self, nums, target):
        # 方法一：四个指针，固定两个，另外两个滑动窗口，去重放里面
        lists = []
        nums.sort()
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                left = j + 1
                right = len(nums) - 1
                while right > left:
                    if nums[i] + nums[j] + nums[left] + nums[right] == target:
                        lists.append((nums[i], nums[j], nums[left], nums[right]))
                        left += 1
                        right -= 1
                    elif nums[i] + nums[j] + nums[left] + nums[right] > target:
                        right -= 1 # 太大了，右指针左移
                    else:
                        left += 1 # 反之
        # 去重
        res = []
        for j in lists:
            if j not in res:
                res.append(j)
        return res
class Solution(object):
    def fourSum(self, nums, target):
        # 方法二：递归，对于n数之和问题，固定第1个数，即变成求n-1数之和的问题，固定前两个数，就变成了求n-2个数之和的问题，最基本的情况就是求两数之和问题
        if len(nums) < 4:
            return []
        def dfs(nums, n, target):
            if len(nums) < n:
                return []
            res = []
            if n == 2:
                left, right = 0, len(nums)-1
                while left < right:
                    if nums[left] + nums[right] == target:
                        res.append([nums[left], nums[right]])
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif nums[left] + nums[right] > target:
                        right -= 1
                    else:
                        left += 1
                return res
            else:
                for first_idx in range(len(nums)):
                    if first_idx > 0 and nums[first_idx] == nums[first_idx-1]:
                        continue
                    subres = dfs(nums[first_idx+1:], n-1, target-nums[first_idx])
                    for i in range(len(subres)):
                        res.append([nums[first_idx]] + subres[i])
                return res
        nums.sort()
        return dfs(nums, 4, target)

平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
输入：c = 5
输出：true
解释：1 1 + 2 2 = 5
输入：c = 3
输出：false
输入：c = 4
输出：true

class Solution(object):
    def judgeSquareSum(self, c):
        # 这种开平方的题都比较死，掌握
        left = 0
        right = int(c**0.5)
        while left <= right:
            tmp = left*left + right*right
            if tmp > c:
                right -= 1
            elif tmp < c:
                left += 1
            else:
                return True
        return False

删除有序数组中的重复项

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

class Solution:
    def removeDuplicates(self, nums): 
        # 快慢指针，把所有重复的值都一点点换到最后
        if not nums:
            return 0
        left, right = 0, 0
        while left < len(nums):
            if nums[left] == nums[right]:
                left += 1
            else:
                right += 1
                nums[right] = nums[left]
        return right + 1

删除有序数组中的重复项 II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]

class Solution(object):
    def removeDuplicates(self, nums):
        left = 0
        right = 0
        while right < len(nums):
            if left < 2 or nums[right] != nums[left-2]:
                nums[left] = nums[right]
                left += 1
            right += 1
        return left
        # 数据结果
        # [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
        # [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
        # [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
        # [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
        # [0, 0, 1, 1, 2, 2, 2, 3, 3, 4]
        # [0, 0, 1, 1, 2, 2, 2, 3, 3, 4]
        # [0, 0, 1, 1, 2, 2, 3, 3, 3, 4]
        # [0, 0, 1, 1, 2, 2, 3, 3, 3, 4]
        # [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]

字符串的排列*

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
输入: s1= “ab” s2 = “eidboaoo”
输出: False

class Solution(object):
    def checkInclusion(self, s1, s2):
        # 因为 s1 的字母的顺序不要求，所以判断是 s2 的子串只要，字母的个数相同即可
        first = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
        second = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
        for i in s1:
            first[i] += 1
        for i in range(len(s2)):
            second[s2[i]] += 1
            # 窗口比s1大时，要把前面的元素删掉
            if i >= len(s1):
                second[s2[i-len(s1)]] -= 1
            if first == second: 
                return True
        return False

滑动窗口最大值*

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
———————- ——-
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

输入：nums = [1], k = 1
输出：[1]

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        # 方法一：使用双端队列，并且存入index
        queue = []
        res = []
        for i in range(len(nums)):
            # 如果当前元素大于单调队列中的尾端元素的话：pop单调队列中的尾端元素
            while queue and nums[queue[-1]] < nums[i]:
                queue.pop()
            queue.append(i)
            # 当单调队列的第一个元素（即最大的元素）不在[i - k + 1, i]，
            # 说明该最大元素在当前的窗口之外，则pop(0)单调队列中的第一个元素
            if queue[0] <= i - k:
                queue.pop(0)
            # 在当前index >= k - 1的时候（即这时候已经能够构成长度为k的窗口）把单调队列的第一个元素加入到结果中去
            if i >= k - 1:
                res.append(nums[queue[0]])
        return res

合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

class Solution:
    def merge(self, nums1, m, nums2, n):
        # 方法一：正向双指针，空间复杂度On
        cur = 0
        pre = 0
        res = []
        nums1[:] = nums1[:m] 
        while cur < m and pre < n:
            if nums1[cur] < nums2[pre]:
                res.append(nums1[cur])
                cur += 1
            else:
                res.append(nums2[pre])
                pre += 1
        if pre < n:
            res += nums2[pre:]
        else:
            res += nums1[cur:]
        nums1[:] = res
        return nums1
        # 方法二：最优解，逆向双指针，空间复杂度是常数，直接在nums1的末尾更新
        cur = m - 1
        pre = n - 1
        tmp = m + n - 1
        while cur >= 0 and pre >= 0:
            if nums1[cur] < nums2[pre]:
                nums1[tmp] = nums2[pre]
                pre -= 1
                tmp -= 1
            else:
                nums1[tmp] = nums1[cur]
                cur -= 1
                tmp -= 1
        # nums2没有遍历完
        nums1[:pre + 1] = nums2[:pre + 1]
        return nums1

调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

class Solution(object):
    def exchange(self, nums):
        # 方法一：暴力法
        odd = []  # 奇数
        even = [] # 偶数
        for i in nums:
            if i % 2 == 0:   # i 是偶数：
                even.append(i)
            else:
                odd.append(i)
        return odd + even
        # 方法二：left向右移找偶数，right向左移找奇数，交换left和right所指数字
        left = 0
        right = len(nums) -1
        while left < right:
            while left < right and nums[left] % 2 == 1:
                left += 1
            while left < right and nums[right] % 2 == 0:
                right -=1
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
        return nums

长度最小的子数组*

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
输入：target = 4, nums = [1,4,4]
输出：1
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

class Solution(object):
    def minSubArrayLen(self, target, nums):
        res = 0
        count = len(nums) + 1
        left = 0
        right = 0
        while right < len(nums):
            res += nums[right]
            while res >= target:
                count = min(right-left+1, count)
                res -= nums[left]
                left += 1
            right += 1
        if count == len(nums) + 1:
            return 0
        else:
            return count

二维数组中的查找（双指针）

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。

class Solution(object):
    def findNumberIn2DArray(self, matrix, target):
        # 从左下角开始判断，如果大target就向上移动，如果小于target就向右移动
        if not matrix:
            return False
        x = 0
        y = len(matrix) - 1
        while x < len(matrix[0]) and y >= 0:
            if matrix[y][x] > target:
                y -= 1
            elif matrix[y][x] < target:
                x += 1
            else:
                return True
        return False
        # 从右上角开始
        if not matrix:
            return False
        x = len(matrix[0]) - 1
        y = 0
        while x >= 0 and y <len(matrix):
            if matrix[y][x] > target:
                x -= 1
            elif matrix[y][x] < target:
                y += 1
            else:
                return True
        return False

旋转矩阵

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
输入：matrix = [[1]]
输出：[[1]]

class Solution(object):
    def rotate(self, matrix):
        # 方法一：只支持正方形
        # 上下翻转
        matrix[:] = matrix[::-1]
        # 左右翻转
        for i in range(len(matrix[0])):
            for j in range(i, len(matrix)):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        return matrix
        # 方法二：只支持正方形，空间复杂度On2
        matrix_new = [[0] * len(matrix) for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix)):
                matrix_new[j][len(matrix)-i-1] = matrix[i][j]
        matrix[:] = matrix_new
        return matrix

二维数组求每列的最小值

martix = [
    [72, 76, 44, 62, 81, 31],
    [54, 36, 82, 71, 40, 45],
    [63, 59, 84, 36, 34, 51],
    [58, 53, 59, 22, 77, 64],
    [35, 77, 60, 76, 57, 44]]
# 方法一：暴力法
res = []
# 因为是6列，所以得把[0]放在前面
for i in range(len(martix[0])):
    tmp = []
    for j in range(len(martix)):
        tmp.append(martix[j][i])
    res.append(min(tmp))
print(res)
# 方法二：翻转过来，如果是正方形可以用上面的方法旋转，如果是长方形翻转需要占用额外的空间，所以用暴力法就行

盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

class Solution(object):
    def maxArea(self, height):
        # 矩阵的面积与两个因素有关
        # 1.两条垂直线的距离
        # 2.两条垂直线其中较短一条的长度
        left = 0
        right = len(height) - 1
        res = 0
        while left < right:
            # 两条垂直线的距离
            min_x = right-left
            # 两条垂直线其中较短一条的长度
            min_y = min(height[right], height[left])
            # 求面积
            res = max(res, min_x * min_y)
            if height[right] > height[left]:
                left += 1
            else:
                right -= 1
        return res

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
输入：height = [4,2,0,3,2,5]
输出：9

class Solution(object):
    def trap(self, height):
        left = 0
        right = len(height) - 1
        leftMax = 0
        rightMax = 0
        # 记录总面积
        res = 0
        while left < right:
            # 使用height[left]和height[right]的值更新leftMax和rightMax的值
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            # 如果height[left] < height[right]，则必有leftMax < rightMax，下标left处能接的雨水量等于leftMax−height[left]，将下标left处能接的雨水量加到能接的雨水总量，然后将left加1（即向右移动一位）
            if height[left] < height[right]:
                res += leftMax - height[left]
                left += 1
            # 如果height[left] >= height[right]，则必有leftMax >= rightMax，下标right处能接的雨水量等于rightMax−height[right]，将下标right 处能接的雨水量加到能接的雨水总量，然后将right减1（即向左移动一位）
            else:
                res += rightMax - height[right]
                right -= 1 
        return res

颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
输入：nums = [2,0,1]
输出：[0,1,2]
输入：nums = [0]
输出：[0]

class Solution(object):
    def sortColors(self, nums): 
        # 方法一：好理解，第一次把0都换回来，第二次再第一次位置的基础上把1都换回来
        cur = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                nums[i], nums[cur] = nums[cur], nums[i]
                cur += 1
        for i in range(cur, len(nums)):
            if nums[i] == 1:
                nums[i], nums[cur] = nums[cur], nums[i]
                cur += 1
        return nums
        # 方法二：双指针，如果是1就直接交换位置，如果是0还需要和1比较一次大小
        p0 = 0
        p1 = 0
        for i in range(len(nums)):
            if nums[i] == 1:
                nums[i], nums[p1] = nums[p1], nums[i]
                p1 += 1
            elif nums[i] == 0:
                nums[i], nums[p0] = nums[p0], nums[i]
                if p0 < p1:
                    nums[i], nums[p1] = nums[p1], nums[i]
                p0 += 1
                p1 += 1
        return nums

螺旋矩阵，顺时针打印矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

class Solution(object):
    def spiralOrder(self, matrix):
        if not matrix: 
            return []
        res = []
        # 表示从左数第l列
        left = 0
        # 总列数
        right = len(matrix[0]) - 1
        # 表示从上数第t层
        above = 0
        # 总层数
        below = len(matrix) - 1
        while True:
            # 从左到右
            for i in range(left, right + 1): 
                res.append(matrix[above][i])
            above += 1
            if above > below: 
                break
            # 从上到下
            for i in range(above, below + 1): 
                res.append(matrix[i][right])
            right -= 1
            if left > right: 
                break
            # 从右到左
            for i in range(right, left - 1, -1): 
                res.append(matrix[below][i])
            below -= 1
            if above > below: 
                break
            # 从下到上
            for i in range(below, above - 1, -1): 
                res.append(matrix[i][left])
            left += 1
            if left > right: 
                break
        return res