• 力扣刷题(代码回忆录)——数组部分

    数组

    1. 数组过于简单，但你该了解这些！
    2. 数组：二分查找
    3. 数组：移除元素
    4. 数组：序数组的平方
    5. 数组：长度最小的子数组
    6. 数组：螺旋矩阵II
    7. 数组：总结篇

     704. 二分查找

    给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
    示例 1:

    1. 输入: nums = [-1,0,3,5,9,12], target = 9
    2. 输出: 4
    3. 解释: 9 出现在 nums 中并且下标为 4

    示例 2:

    1. 输入: nums = [-1,0,3,5,9,12], target = 2
    2. 输出: -1
    3. 解释: 2 不存在 nums 中因此返回 -1

    提示：

    1. 你可以假设 nums 中的所有元素是不重复的。
    2. n 将在 [1, 10000]之间。
    3. nums 的每个元素都将在 [-9999, 9999]之间。

    算法思路： 二分查找模板

    1. class Solution {
    2. public:
    3.     int search(vector<int>& nums, int target) {
    4.         int left = 0;
    5.         int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
    6.         while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
    7.             int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
    8.             if (nums[middle] > target) {
    9.                 right = middle - 1; // target 在左区间，所以[left, middle - 1]
    10.             } else if (nums[middle] < target) {
    11.                 left = middle + 1; // target 在右区间，所以[middle + 1, right]
    12.             } else { // nums[middle] == target
    13.                 return middle; // 数组中找到目标值，直接返回下标
    14.             }
    15.         }
    16.         // 未找到目标值
    17.         return -1;
    18.     }
    19. };

     实现代码：

    1. class Solution:
    2.     def search(self, nums: List[int], target: int) -> int:
    3.         left, right = 0, len(nums)-1
    4.         while(left <= right):
    5.             mid = int((left + right) / 2)
    6.             if(nums[mid] == target):
    7.                 return mid
    8.             elif(nums[mid] > target):
    9.                 right = mid - 1
    10.             else:
    11.                 left = mid + 1
    12.         return -1

    类似的二分查找的题目： 

    类似题目1：35. 搜索插入位置

    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

    请必须使用时间复杂度为 O(log n) 的算法。

    示例 1:

    1. 输入: nums = [1,3,5,6], target = 5
    2. 输出: 2

    示例 2:

    1. 输入: nums = [1,3,5,6], target = 2
    2. 输出: 1

    示例 3:

    1. 输入: nums = [1,3,5,6], target = 7
    2. 输出: 4

    提示:

    • 1 <= nums.length <= 104
    • -104 <= nums[i] <= 104
    • nums 为 无重复元素 的 升序 排列数组
    • -104 <= target <= 104

     实现代码：

    注意：左指针left指向最小大于target的值（也叫target右侧最靠近的值），右指针right会指向最大小于target的值（也叫target左侧最靠近的值）。

    1. class Solution:
    2.     def searchInsert(self, nums: List[int], target: int) -> int:
    3.         left, right = 0, len(nums)-1
    4.         while(left <= right):
    5.             mid = int((left + right) / 2)
    6.             if(nums[mid] == target):
    7.                 return mid
    8.             elif(nums[mid] > target):
    9.                 right = mid - 1#右指针会指向最大小于target的值
    10.             else:
    11.                 left = mid + 1#左指针指向最小大于target的值
    12.         return left

    类似题目2 ：34. 在排序数组中查找元素的第一个和最后一个位置（题目很新）

    给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

    如果数组中不存在目标值 target，返回 [-1, -1]。

    你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

    示例 1：

    1. 输入：nums = [5,7,7,8,8,10], target = 8
    2. 输出：[3,4]

    示例 2：

    1. 输入：nums = [5,7,7,8,8,10], target = 6
    2. 输出：[-1,-1]

    示例 3：

    1. 输入：nums = [], target = 0
    2. 输出：[-1,-1]

    提示：

    • 0 <= nums.length <= 105
    • -109 <= nums[i] <= 109
    • nums 是一个非递减数组
    • -109 <= target <= 109

    算法分析：

    寻找target在数组里的左右边界，有如下三种情况：

    • 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
    • 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
    • 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

    这三种情况都考虑到，说明就想的很清楚了。

    接下来，在去寻找左边界，和右边界了。

    采用二分法来去寻找左右边界，为了让代码清晰，我分别写两个二分来寻找左边界和右边界。

    实现代码：

    1. class Solution:
    2.     def searchRange(self, nums: List[int], target: int) -> List[int]:
    3.         if(len(nums) == 0):
    4.             return [-1, -1]
    5.         
    6.         def findLeftBound(nums, target):#找到左边界
    7.             left, right = 0, len(nums)-1
    8.             while(left <= right):
    9.                 mid = int(left+(right-left)/2)
    10.                 if(nums[mid] == target):
    11.                 # 为了找到左边界，在遇到target值的时候还要继续往左边找
    12.                     right = mid -1
    13.                 elif(nums[mid] > target):
    14.                     right = mid - 1#右指针会指向最大小于target的值
    15.                 else:
    16.                     left = mid + 1#左指针指向最小大于target的值
    17.             if(left >= len(nums) or nums[left] != target):
    18.                 return -1
    19.             else:
    20.                 return left
    21.  
    22.         def findRightBound(nums, target):#找到右边界
    23.             left, right = 0, len(nums)-1
    24.             while(left <= right):
    25.                 mid = int(left+(right-left)/2)
    26.                 if(nums[mid] == target):
    27.                 # 为了找到右边界，在遇到target值的时候还要继续往左边找
    28.                     left = mid + 1
    29.                 elif(nums[mid] > target):
    30.                     right = mid - 1#右指针会指向最大小于target的值
    31.                 else:
    32.                     left = mid + 1#左指针指向最小大于target的值
    33.             if(right < 0 or nums[right] != target):
    34.                 return -1
    35.             else:
    36.                 return right
    37.  
    38.         leftBound = findLeftBound(nums, target)
    39.         rightBoud = findRightBound(nums, target)
    40.         return[leftBound, rightBoud]

    类似题目3：69. x 的平方根 

    给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

    由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

    注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

    示例 1：

    1. 输入：x = 4
    2. 输出：2

    示例 2：

    1. 输入：x = 8
    2. 输出：2
    3. 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

    提示：

    • 0 <= x <= 231 - 1

    算法思想： 

    由于 x 平方根的整数部分 ans 是满足 k ^ 2 ≤ x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。
    二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。

    实现代码：

    1. class Solution:
    2.     def mySqrt(self, x: int) -> int:
    3.         left, right = 0, x
    4.         while(left <= right):
    5.             mid = (left + right) // 2 #//表示向下取整
    6.             if(mid **2 == x):
    7.                 return mid
    8.             elif(mid **2 < x):
    9.                 left = mid + 1#左指针指向最小大于target的值
    10.             else:
    11.                 right = mid - 1#右指针会指向最大小于target的值
    12.         return right

    类似题目4：367. 有效的完全平方数

    给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

    进阶：不要 使用任何内置的库函数，如  sqrt 。

    示例 1：

    1. 输入：num = 16
    2. 输出：true

    示例 2：

    1. 输入：num = 14
    2. 输出：false

    提示：

    • 1 <= num <= 2^31 - 1

     实现代码：（算法思路跟这个题目69. x 的平方根一样）：

    1. class Solution:
    2.     def isPerfectSquare(self, num: int) -> bool:
    3.         left, right = 1, num
    4.         while(left <= right):
    5.             mid = (left + right) // 2
    6.             if(mid **2 == num):
    7.                 return True
    8.             elif(mid **2 < num):
    9.                 left = mid + 1
    10.             else:
    11.                 right = mid - 1
    12.         return False

    127. 移除元素-双指针法（快慢指针法）

    给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

    不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

    元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

    算法思想：

     实现代码：

    1. class Solution:
    2.     def removeElement(self, nums: List[int], val: int) -> int:
    3.     #双指针左移覆盖法
    4.         left = 0#左指针left 指向下一个将要赋值的位置
    5.         for right in range(len(nums)):#右指针 right指向当前将要处理的元素
    6.             if(nums[right] != val):
    7.                 nums[left] = nums[right]
    8.                 left += 1
    9.         return left

     类似题目1 26. 删除有序数组中的重复项 - 双指针之快慢指针

    给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

    由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

    将最终结果插入 nums 的前 k 个位置后返回 k 。

    不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    解题思路：
    题意：删除有序数组重复项，把去重后的数字放在输入数组的前面 n 个位置，返回 n.

    看到题目标题的第一反应，当然是用 set ！set 就是为了实现去重的。但是题目要求我们进行原地操作，并且时间复杂度是 O(1)，因此就不能开辟另外的空间。

    双指针：
    题目需要我们把去重后的结果保存到原本的数组中，所以想到必须有一个指针指向当前需要把结果放在哪个位置。还要一个指针指向当前应该放到哪个元素。

    • 慢指针作为基准，快指针用于寻找与慢指针不同的元素。
    • 如果快指针和慢指针指向的元素不等，则把快指针指向的元素放到慢指针的下一个位置。
    • 慢指针右移，把新的元素作为基准。

    实现代码：

    1. class Solution:
    2.     def removeDuplicates(self, nums: List[int]) -> int:
    3.         left = 0#慢指针
    4.         for right in range(1, len(nums)):#right表示快指针
    5.             if(nums[left] != nums[right]):
    6. #如果快指针和慢指针指向的元素不等，则把快指针指向的元素放到慢指针的下一个位置。
    7.                 left += 1
    8.                 nums[left] = nums[right]
    9.         return left+1

    类似题目2 283. 移动零

    给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

    请注意 ，必须在不复制数组的情况下原地对数组进行操作。

    实现代码：（算法思想同 类似题目1 26. 删除有序数组中的重复项 ） 

    1. class Solution:
    2.     def moveZeroes(self, nums: List[int]) -> None:
    3.         """
    4.         Do not return anything, modify nums in-place instead.
    5.         """
    6.         left = 0
    7.         for right in range(len(nums)):
    8.             if(nums[right] != 0):
    9.                 nums[left] = nums[right]
    10.                 left += 1
    11.         for i in range(left, len(nums)):
    12.             nums[i] = 0

    类似题目3：977. 有序数组的平方

    给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

    示例 1：

    1. 输入：nums = [-4,-1,0,3,10]
    2. 输出：[0,1,9,16,100]
    3. 解释：平方后，数组变为 [16,1,0,9,100]
    4. 排序后，数组变为 [0,1,9,16,100]

    示例 2：

    1. 输入：nums = [-7,-3,2,3,11]
    2. 输出：[4,9,9,49,121]

    提示：

    • 1 <= nums.length <= 104
    • -104 <= nums[i] <= 104
    • nums 已按 非递减顺序 排序

    算法分析：

    同样地，我们可以使用两个指针分别指向位置 000 和 n−1n-1n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。

    实现代码：

    1. class Solution:
    2.     def sortedSquares(self, nums: List[int]) -> List[int]:
    3.         # for i in range(len(nums)):
    4.         #     nums[i] = nums[i]**2
    5.         # nums = sorted(nums)
    6.         # return nums
    7.         res = [0 for _ in range(len(nums))]
    8.         left, right, pos = 0, len(nums)-1, len(nums)-1
    9.         #从最后开始放较大的那个数字
    10.         #因为left或者right开始的时候一定是指向那个平方最大的那个数
    11.         while(left <= right):
    12.             if((nums[left] **2) > (nums[right] **2)):
    13.                 res[pos] = nums[left] **2
    14.                 left += 1
    15.             else:
    16.                 res[pos] = nums[right] **2
    17.                 right -= 1
    18.             pos -= 1
    19.         return res

    类似题目4：844. 比较含退格的字符串

    给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

    注意：如果对空文本输入退格字符，文本继续为空。

    示例 1：

    1. 输入：s = "ab#c", t = "ad#c"
    2. 输出：true
    3. 解释：s 和 t 都会变成 "ac"。

    示例 2：

    1. 输入：s = "ab##", t = "c#d#"
    2. 输出：true
    3. 解释：s 和 t 都会变成 ""。

    示例 3：

    1. 输入：s = "a#c", t = "b"
    2. 输出：false
    3. 解释：s 会变成 "c"，但 t 仍然是 "b"。

    提示：

    • 1 <= s.length, t.length <= 200
    • s 和 t 只含有小写字母以及字符 '#'

    算法分析：

    采用类似栈的思想，当字符串s或者t的第i个字符不为空时，就把第i个字符入栈，当第i个字符为#时，就把栈顶元素弹出（前提时栈不为空时才可以进行此操作），最后再把栈里的元素转化为字符串再比较两者是否相等。

    实现代码：

    1. class Solution:
    2.     def backspaceCompare(self, s: str, t: str) -> bool:
    3.         listS = []
    4.         for i in range(len(s)):
    5.             if(s[i] != '#'):
    6.                 listS.append(s[i])
    7.             else:
    8.                 if(len(listS) != 0):#当列表不为空时，才能弹出元素
    9.                     listS.pop()
    10.         s = ''.join(listS)#列表类型转化为字符串类型
    11.  
    12.         listT = []
    13.         for i in range(len(t)):
    14.             if(t[i] != '#'):
    15.                 listT.append(t[i])
    16.             else:
    17.                 if(len(listT) != 0):#当列表不为空时，才能弹出元素
    18.                     listT.pop()
    19.         t = ''.join(listT)#列表类型转化为字符串类型
    20.  
    21.         return s == t

    类似题目5：15. 三数之和 -三指针+排序

    给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

    你返回所有和为 0 且不重复的三元组。

    注意：答案中不可以包含重复的三元组。

    示例 1：

    1. 输入：nums = [-1,0,1,2,-1,-4]
    2. 输出：[[-1,-1,2],[-1,0,1]]
    3. 解释：
    4. nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
    5. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
    6. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
    7. 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
    8. 注意，输出的顺序和三元组的顺序并不重要。

    示例 2：

    1. 输入：nums = [0,1,1]
    2. 输出：[]
    3. 解释：唯一可能的三元组和不为 0 。

    示例 3：

    1. 输入：nums = [0,0,0]
    2. 输出：[[0,0,0]]
    3. 解释：唯一可能的三元组和为 0 。

    提示：

    • 3 <= nums.length <= 3000
    • -105 <= nums[i] <= 105

    算法思想：

      

    实现代码： 

    1. class Solution:
    2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
    3.         res = []
    4.         if(not nums or len(nums) < 3 ):
    5.             return []
    6.         nums.sort()
    7.         for i in range(len(nums)):
    8.             # 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回[]
    9.             if(nums[i] > 0):
    10.                 break
    11.             # 对于重复元素：跳过，避免出现重复解
    12.             if(i>0 and nums[i-1] == nums[i]):
    13.                  continue
    14.             l = i+1
    15.             r = len(nums)-1
    16.             # 令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
    17.             while(l < r):
    18.                 if(nums[i] + nums[l] + nums[r] == 0):
    19.                     res.append([nums[i], nums[l], nums[r]])
    20.             # 当 nums[i]+nums[L]+nums[R]==0时
    21.             #执行循环，判断左界和右界是否和下一位置重复，去除重复解
    22.                     while(l < r and nums[l] == nums[l+1]):
    23.                         l += 1
    24.                     while(l < r and nums[r-1] == nums[r]):
    25.                         r -= 1
    26.             # 并同时将 L,R 移到下一位置，寻找新的解
    27.                     l += 1
    28.                     r -= 1
    29.                 # 若和大于 0，说明 nums[r] 太大，r左移
    30.                 elif(nums[i] + nums[l] + nums[r] > 0):
    31.                     r -= 1
    32.                 # 若和小于 0，说明 nums[l] 太小，l 右移
    33.                 else:
    34.                     l += 1 
    35.         return res

    写法2更利于理解： 

    1. class Solution:
    2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
    3.         res, sum = [], 0
    4.         nums.sort()
    5.         if(not nums and len(nums) < 3):
    6.             return []
    7.         for i in range(len(nums)-2):
    8.         #在已经排好序的数组且为正数的情况下，当第一个数大于0时，后面的情况可以不用看了
    9.             if(nums[i] > 0):#剪枝
    10.                 break
    11.             
    12.             l = i + 1
    13.             r = len(nums) - 1
    14.             while(l < r):
    15.                 sum = nums[i] + nums[l] + nums[r]
    16.                 if(sum == 0 and [nums[i],nums[l],nums[r]] not in res):
    17.                     res.append([nums[i], nums[l], nums[r]])
    18.                     l += 1
    19.                     r -= 1
    20.                 elif(sum > 0):
    21.                     r -= 1
    22.                 else:
    23.                     l += 1
    24.         return res

    类似题目6：18. 四数之和 

    给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

    • 0 <= a, b, c, d < n
    • a、b、c 和 d 互不相同
    • nums[a] + nums[b] + nums[c] + nums[d] == target

    你可以按 任意顺序 返回答案 。

    示例 1：

    1. 输入：nums = [1,0,-1,0,-2,2], target = 0
    2. 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

    示例 2：

    1. 输入：nums = [2,2,2,2,2], target = 8
    2. 输出：[[2,2,2,2]]

    提示：

    • 1 <= nums.length <= 200
    • -109 <= nums[i] <= 109
    • -109 <= target <= 109

    算法思路：

    本质上同15. 三数之和算法如出一辙，只是在原来的基础上又套了一层for循环

    实现代码：

    1. class Solution:
    2.     def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    3.         res, sum = [], 0
    4.         nums.sort()
    5.         if(not nums and len(nums) < 4):
    6.             return []
    7.         for i in range(len(nums)-3):
    8.         #在已经排好序的数组且为正数的情况下，当第一个数大于target时，后面的情况可以不用看了
    9.             if(nums[i] > 0 and nums[i] > target):#剪枝
    10.                 break
    11.             for j in range(i+1, len(nums)-2):
    12.                 l = j + 1
    13.                 r = len(nums) - 1
    14.                 while(l < r):
    15.                     sum = nums[i] + nums[j] + nums[l] + nums[r]
    16.                     if(sum == target and [nums[i],nums[j],nums[l],nums[r]] not in res):
    17.                         res.append([nums[i],nums[j],nums[l],nums[r]])
    18.                         l += 1
    19.                         r -= 1
    20.                     elif(sum > target):
    21.                         r -= 1
    22.                     else:
    23.                         l += 1
    24.         return res
    25.

    209. 长度最小的子数组-滑动窗口

    滑动窗口模板：

    1. def findSubArray(nums):
    2.     N = len(nums) # 数组/字符串长度
    3.     left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    4.     sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
    5.     res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    6.     while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
    7.         sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
    8.         while 区间[left, right]不符合题意: # 此时需要一直移动左指针，直至找到一个符合题意的区间
    9.             sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
    10.             left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
    11.         # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
    12.         res = max(res, right - left + 1) # 需要更新结果
    13.         right += 1 # 移动右指针，去探索新的区间
    14.     return res

    给定一个含有 n 个正整数的数组和一个正整数 target 。

    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

    示例 1：

    1. 输入：target = 7, nums = [2,3,1,2,4,3]
    2. 输出：2
    3. 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

    示例 2：

    1. 输入：target = 4, nums = [1,4,4]
    2. 输出：1

    示例 3：

    1. 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
    2. 输出：0

    提示：

    1 <= target <= 109
    1 <= nums.length <= 105
    1 <= nums[i] <= 105

    算法思路:

    将数组nums里的元素依次一个个入队window，要是sum(window)超过target值就减掉一个，要是没超过就继续加，直至满足条件。
    实现代码：

    1. class Solution:
    2.     def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    3.         left = right = 0 #滑动窗口的左右两个端点
    4.         minLen = float('inf') #初始化长度最小的 连续子数组的长度
    5.         sum = 0 #记录当前窗口里元素的之和
    6.         length = len(nums) #记录列表里元素的个数
    7.         while(right < length):
    8.             sum += nums[right]
    9.             while(sum >= target):
    10.                 sum -= nums[left] # 去掉左侧的数
    11.                 minLen = min(minLen, right - left + 1)
    12.                 left += 1 # 左边要剔除的数可能不止一个
    13.             right += 1
    14.         if(minLen == float('inf')): #target值不在列表里
    15.             return 0
    16.         else:
    17.             return minLen

    更多滑动窗口题目和内容可以参考：

    力扣---字符串系列题目_金州饿霸的博客-CSDN博客

    59. 螺旋矩阵 II-四指针（上下左右）边界收缩

    给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

    算法思路：(本质是把数顺时针填入矩阵中)

    实现代码：

    1. class Solution:
    2.     def generateMatrix(self, n: int) -> List[List[int]]:
    3.         l, r, t, b = 0, n - 1, 0, n - 1#左右上下的边界, 同时t/l也表示行，b/r也表示列
    4.         res = [[0 for _ in range(n)] for _ in range(n)]
    5.         num = 1#表示要填充的数字
    6.         while(num <= n**2):
    7.             for i in range(l, r + 1):# 从左到右填充，相当于缩小上边界
    8.                 res[t][i] = num
    9.                 num += 1
    10.             t += 1#从左到右填完后，上边界 t += 1，相当于上边界向内缩 1
    11.             for i in range(t, b + 1):#从上向下填充，相当于缩小右边界
    12.                 res[i][r] = num
    13.                 num += 1
    14.             r -= 1
    15.             for i in range(r, l-1, -1):# 从右向左填充，相当于缩小下边界
    16.                 res[b][i] = num
    17.                 num += 1
    18.             b -= 1
    19.             for i in range(b, t-1, -1):# 从下向上填充，相当于缩小左边界
    20.                 res[i][l] = num
    21.                 num += 1
    22.             l += 1
    23.         return res
    24.

    类似题目1：54. 螺旋矩阵

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

    算法思想：（本质上是把矩阵里的数顺时针读出来）

    算法思想同上面的题目59. 螺旋矩阵 II

    实现代码：

    1. class Solution:
    2.     def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    3.         l, r, t, b = 0, len(matrix[0]) - 1, 0, len(matrix) - 1
    4.         res = []
    5.         length = len(matrix[0]) * len(matrix) #矩阵元素个数（列*行）
    6.         while(length > 0):
    7.             for i in range(l, r + 1):# 从左到右填充，相当于缩小上边界
    8.                 if(length > 0):
    9.                     res.append(matrix[t][i])
    10.                     length -= 1
    11.             t += 1#从左到右填完后，上边界 t += 1，相当于上边界向内缩 1
    12.             for i in range(t, b + 1):#从上向下填充，相当于缩小右边界
    13.                 if(length > 0):
    14.                     res.append(matrix[i][r])
    15.                     length -= 1
    16.             r -= 1
    17.             for i in range(r, l-1, -1):# 从右向左填充，相当于缩小下边界
    18.                 if(length > 0):
    19.                     res.append(matrix[b][i])
    20.                     length -= 1
    21.             b -= 1
    22.             for i in range(b, t-1, -1):# 从下向上填充，相当于缩小左边界
    23.                 if(length > 0):
    24.                     res.append(matrix[i][l])
    25.                     length -= 1
    26.             l += 1
    27.         return res

    回溯算法 

     46. 全排列

    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

    1. 示例 1：
    2.  
    3. 输入：nums = [1,2,3]
    4. 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    1. 示例 2：
    2.  
    3. 输入：nums = [0,1]
    4. 输出：[[0,1],[1,0]]
    1. 示例 3：
    2.  
    3. 输入：nums = [1]
    4. 输出：[[1]]

    提示：

    • 1 <= nums.length <= 6
    • -10 <= nums[i] <= 10
    • nums 中的所有整数 互不相同

    算法思想：
    （1）方法一：调用库函数

    利用itertools库中的permutations方法。

    实现代码：

    1. class Solution:
    2.     def permute(self, nums: List[int]) -> List[List[int]]:
    3.         all_permutation = list(itertools.permutations(nums))
    4.         return all_permutation

    （2）方法二：递归法 （下面是全排列的模板可以记住）

     实现代码：

    1. class Solution:
    2.     def permute(self, nums: List[int]) -> List[List[int]]:
    3.         def backtrack(position, end):
    4.             if position == end:
    5.                 res.append(nums[:])
    6.             else:
    7.                 for index in range(position, end):
    8.                     nums[index], nums[position] = nums[position], nums[index]#交换两个值的位置
    9.                     backtrack(position + 1, end)
    10.                     nums[index], nums[position] = nums[position], nums[index]
    11.         res = []
    12.         backtrack(0, len(nums))
    13.         return res

    47. 全排列 II

    给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

    示例 1：

    1. 输入：nums = [1,1,2]
    2. 输出：
    3. [[1,1,2],
    4.  [1,2,1],
    5.  [2,1,1]]

    示例 2： 

    1. 输入：nums = [1,2,3]
    2. 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    3.

    提示： 

    1 <= nums.length <= 8
    -10 <= nums[i] <= 10

    算法思路：

    （1）方法一：库函数➕set集合剪枝去重

    这题主要是在全排列的基础上减枝，就是将全排列的结果重复的排列去除掉（因为给的元素可能有重复值），所以可以用集合set去除重复值，然后再转为list值。

    实现代码：

    1. class Solution:
    2.     def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    3.         all_permutation = list(itertools.permutations(nums))
    4.         res = set(all_permutation)
    5.         return list(res)

    （2）方法二：递归+剪枝去重 

    去重主要靠这一步：

    nums[:] not in res
    1. class Solution:
    2.     def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    3.         def backtrack(position, end):
    4.             if(position == end and nums[:] not in res):#减枝去重复
    5.                 res.append(nums[:])
    6.             else:
    7.                 for index in range(position, end):
    8.                     nums[index], nums[position] = nums[position], nums[index]#交换两个值的位置
    9.                     backtrack(position + 1, end)
    10.                     nums[index], nums[position] = nums[position], nums[index]
    11.         res = []
    12.         backtrack(0, len(nums))
    13.         return res

    48. 旋转图像

    给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

    你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

     算法思想：

    （1）方法一：

    直接开辟一个O(n^2)的空间，然后按自下而上，自左到右的顺序遍历，最终把结果存起来。

    实现代码：

    1. class Solution:
    2.     def rotate(self, matrix: List[List[int]]) -> None:
    3.         """
    4.         Do not return anything, modify matrix in-place instead.
    5.         """
    6.         res = []
    7.         for j in range(len(matrix[0])):#控制矩阵的列
    8.             temp = []
    9.             for i in range(len(matrix)-1, -1, -1):#逆序按行遍历
    10.                 temp.append(matrix[i][j])
    11.             res.append(temp)
    12.         for i in range(len(matrix)):
    13.             for j in range(len(matrix[0])):
    14.                 matrix[i][j] = res[i][j]

    （2）方法二：

    对于一个矩阵，要一层一层旋转90°实现起来很复杂。不妨先想想，对于矩阵中值的交换，有哪些操作是比较方便的：

    • 对单行或单列元素反转
    • 沿对角线交换对角线两侧的元素

    实现代码：

    1. class Solution:
    2.     def rotate(self, matrix: List[List[int]]) -> None:
    3.         """
    4.         Do not return anything, modify matrix in-place instead.
    5.         """
    6.         for i in range(len(matrix)):#交换对角线两边的元素
    7.  # 注意这里j的范围 如果j的范围也是0到n-1那么会出现交换后又交换回来等于没有交换
    8.             for j in range(i):
    9.                 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    10.         for line in matrix:#按行取反
    11.             line.reverse()

    78. 子集

    给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

    解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

    示例 1：

    1. 输入：nums = [1,2,3]
    2. 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

    示例 2：

    1. 输入：nums = [0]
    2. 输出：[[],[0]]

    提示：

    • 1 <= nums.length <= 10
    • -10 <= nums[i] <= 10
    • nums 中的所有元素 互不相同

    算法思想：

    有一种思想比较巧妙，可以叫按位对应法。如集合A={a,b,c},对于任意一个元素，在每个子集中，要么存在，要么不存在。也就是说n个元素的集合，它一共有2^n个子集，那么这2^n子集对应整数为0-2^n-1,这些整数可以用n位的二进制数来表示，并且每个子集中的元素存在与否也可以用这n位来表示，1表示在子集中，0表示不在子集中。

    映射为子集：

    类似的图解：

    实现代码： 

    1. class Solution:
    2.     def subsets(self, nums: List[int]) -> List[List[int]]:
    3.         res = []
    4.         for i in range(2 ** len(nums)):#n个元素的集合共有2^n个子集
    5.             temp = []#存放一个子集
    6.             for j in range(len(nums)):#n位二进制数来表示一个子集里的元素，1表示该元素在子集里，0表示不在子集里
    7.                 if((i >> j) % 2 == 1):#按位对应,看每一位是否为1，为1表示该元素在子集中，那么就加入temp
    8.                     temp.append(nums[j])
    9.             res.append(temp)
    10.         return res

    90. 子集 II

    给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

    解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

    示例 1：

    1. 输入：nums = [1,2,2]
    2. 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

    示例 2：

    1. 输入：nums = [0]
    2. 输出：[[],[0]]

    提示：

    • 1 <= nums.length <= 10
    • -10 <= nums[i] <= 10

    算法思想：

    跟上面的思路一模一样，只不过多了一个排序去重的步骤：

    1. finalRes = []
    2. for i in range(len(res)):
    3.     res[i] = sorted(res[i])
    4. for i in range(len(res)):
    5.     if(res[i] not in finalRes):
    6.         finalRes.append(res[i])

    实现代码：

    1. class Solution:
    2.     def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    3.         res = []
    4.         for i in range(2 ** len(nums)):#n个元素的集合共有2^n个子集
    5.             temp = []#存放一个子集
    6.             for j in range(len(nums)):#n位二进制数来表示一个子集里的元素，1表示该元素在子集里，0表示不在子集里
    7.                 if((i >> j) % 2 == 1):#按位对应,看每一位是否为1，为1表示该元素在子集中，那么就加入temp
    8.                     temp.append(nums[j])
    9.             res.append(temp)#res里面可能有重复的子集，只不过因为元素的顺序不同而看着不一样
    10.         finalRes = []
    11.         for i in range(len(res)):#排序去重
    12.             res[i] = sorted(res[i])
    13.         for i in range(len(res)):#去重
    14.             if(res[i] not in finalRes):
    15.                 finalRes.append(res[i])
    16.         return finalRes
    17.

     

  • 相关阅读:
    苹果曝出严重安全漏洞，黑客可全面接管设备！！！
    离线数仓建设
    SANSAN新鲜事｜对接摄像头？一文读懂哪种方式适合你
    代理模式（初学）
    《Translating Images into Maps》论文笔记
    Python3 + Appium + 安卓模拟器实现APP自动化测试并生成测试报告
    JAVA毕业设计分享网站计算机源码+lw文档+系统+调试部署+数据库
    服务器上设置pnpm环境变量
    Seata概述基础
    【学习笔记】数位dp
  • 原文地址：https://blog.csdn.net/wangjian530/article/details/127915996