普通数组

53.最大子数组和（中等）

 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

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

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans=float('-inf')
        a=0
        for num in nums:
            a = max(num, a + num)  # 要么重新开始，要么继续累加
            ans = max(ans, a)  # 更新答案
            
        return ans

这个太简单了，和洛谷的p1115一样，那个用c++写了题解可以去主页看。

不要想得太复杂！！！

从第二个输入的开始，判断它加上上一个是不是会比本身变得更大，如果更大，那就把它俩的和作为现在的最大值，然后再到第三个，看第三个加上之前两个的和是不是更大，如果更大，就将这个数与之前的和相加成为新的最大值，如此递推；如果更小，就抛弃前面的和，自己作为最大值，再往下递推。

也就是说要么以当前值重新开始，要么继续在之前的和上累加。

感觉说的不太清楚，看看大佬的解释！！

重点是要从自己往前加前面的最大和，而不是往后！！！
 

56. 合并区间（中等）

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
          intervals.sort()
          ans=[]
          for p in intervals:
            if ans and p[0]<=ans[-1][1]:
                ans[-1][1]=max(ans[-1][1],p[1])
            else:
                ans.append(p)
          return ans

首先把数组按照第一个值进行排序，直接用sort函数就是按照第一个值排序。如果要按照第二个的话就可以写成intervals.sort(key:lambda p:p[1])。

遍历intervals里面的数组，第一次开始遍历ans还为空，所以直接把第一组数组p加入到ans里去。从第二组开始判断数组p的左边界是不是小于或等于上一个已经放到ans里的区间的右边界，如果是，就可以合并，那么ans里上一个区间的右边界就变成当前右边界和p的右边界的最大值。

如果p左边界大于ans上一个区间的右边界，说明没有重叠，那么把当前的p加入到ans里去。

最后返回ans。

​189. 轮转数组（中等​）

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(i,j)->None:
            while i<j:
                nums[i],nums[j]=nums[j],nums[i]
                i+=1
                j-=1
        n=len(nums)
        k%=n
        reverse(0,n-1)
        reverse(0,k-1)
        reverse(k,n-1)

首先我们来理解一下为什么向右轮转k个位置可以通过反转三次来得到。

       先把当前的数组分为两部分[A,B]，这里的A是前n-k个数字，B是后k个数字。我们想要让数组向右轮转k个数字也就是把数组变为[B,A]。此时我们先将数组全部反转，数组会变成[B',A']，这里的B'是反转后的B，A'也就是反转后的A。想要得到[B,A]只需要把B'和A'再次反转即可。

然后我们来定义反转函数，将左指针i指向当前要反转的起始位置，右指针j指向要反转的末尾位置，当i小于j时，将i和j指向的值互换，然后i向右移，j向左移，直到它们指向同一个位置或者是交错开。

k%=n这一步的目的是保证k的值永远在[0,n-1]这个区间里面，因为如果k大于等于n，那么轮转的位置也就等于k-n个，例如现在有7个数字，你要向右轮转8次，他的效果就等于向右轮转一次。

最后，经过三次反转就得到了最后的数组。

238. 除了自身以外数组的乘积（中等）

 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在  32 位 整数范围内

本来想的很简单，直接用数组切片用函数prod把前后切片乘积再相乘，但是时间过不去。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer=[]
        for i in range(len(nums)):
            ans=prod(nums[0:i])*prod(nums[i+1:len(nums)])
            answer.append(ans)
        return answer

然后想到下面的解法：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n=len(nums)
        rs_l,rs_r=[1]*n,[1]*n
        for i in range(1,n):
            rs_l[i]=rs_l[i-1]*nums[i-1]
        for i in range(n-2,-1,-1):
            rs_r[i]=rs_r[i+1]*nums[i+1]
        for i in range(n):
            rs_l[i]*=rs_r[i]

        return rs_l

其实这个也很好理解，就是前缀积乘后缀积就是当前位置的答案。

首先将前缀积和后缀积用两个长度与nums长度一样，数值全为1的数组表示。

然后计算每个位置的前缀积，第一个位置的前缀积就是1，从第二个位置开始遍历，第二个位置的前缀积就等于第一个位置的数值乘以第一个位置的前缀积，第三个就等于第二个位置的数值乘以第二个位置的前缀积，以此类推。

再计算每个位置的后缀积，从n-2开始，也就是倒数第二个位置开始，因为倒数第一个位置的后缀积一定是1，然后往左遍历，步长为-1。和前缀积一样，倒数第二个位置就等于倒数第一个位置的数值乘以它的后缀积，三就等于二的数值乘以二的后缀积，以此类推。

最后把每个位置的前缀积和后缀积乘起来就可以啦！

41. 缺失的第一个正数（困难）

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

首先想到直接排序：

def firstMissingPositive_sort(nums):
    nums.sort()  # O(n log n)，不满足要求
    missing = 1
    for num in nums:
        if num == missing:
            missing += 1
    return missing

超出时间限制，所以我们用原地哈希的办法：

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n=len(nums)
        for i in range(n):
            
            while 1<=nums[i]<=n and nums[nums[i]-1]!=nums[i]:
                j=nums[i]-1
                nums[i],nums[j]=nums[j],nums[i]
        for i in range(n):
            if nums[i]!=i+1:
                return i+1
        return n+1

这里的主要思路就是

• 将每个正整数 x 放到数组下标为 x-1 的位置

• 遍历数组，找到第一个 nums[i] ≠ i+1 的位置

• 返回 i+1

最主要的while循环的意思是只要当前位置的值是有效的正数，并且它不在正确的位置上，就一直交换。

1 <= nums[i] <= n
        只处理值在 [1, n] 范围内的数字
        负数、0、大于 n 的数都忽略（它们不影响结果）

nums[nums[i] - 1] != nums[i]
        检查：值为 x 的数是否在下标为 x-1 的位置上？
        比如：数字 3 应该在下标 2 的位置
        如果 nums[2]已经是 3 了，就不需要交换
        如果 nums[2]不是 3，才需要交换

矩阵

73.矩阵置零（中等）

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

首先想到直接复制一个一样的矩阵

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        # 复制一个完全一样的矩阵
        copy = [row[:] for row in matrix]
        
        # 遍历原矩阵
        for i in range(m):
            for j in range(n):
                if copy[i][j] == 0:  # 用copy来判断
                    # 将原矩阵的整行整列设为0
                    for k in range(n):  # 行置零
                        matrix[i][k] = 0
                    for k in range(m):  # 列置零
                        matrix[k][j] = 0

下面是使用O（m+n）的额外空间

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m,n=len(matrix),len(matrix[0])
        rz=[False]*m
        cz=[False]*n
        for i in range(m):
            for j in range(n):
                if matrix[i][j]==0:
                    rz[i]=True
                    cz[j]=True
        for i in range(m):
            for j in range(n):
                if rz[i] or cz[j]:
                    matrix[i][j]=0        

这里是用俩个全为false的数组存储这一行和这一列是否有0存在。

遍历metrix，如果当前位置为0，那么rz对应的这一行至True，代表这一行有0，列也一样。

最后如果这一行或者一列为true，那这个元素就置零。

54.螺旋矩阵（中等）

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

示例 1：

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

示例 2：

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

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        left,right,top,below=0,len(matrix[0])-1,0,len(matrix)-1
        res=[]
        while True:
            for i in range(left,right+1): res.append(matrix[top][i])
            top+=1
            if top>below: break
            for i in range(top,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 top>below: break
            for i in range(below,top-1,-1): res.append(matrix[i][left])
            left+=1
            if left>right: break
        return res
        

主要思想是设立上下左右四个边界，根据边界打印，打印完之后边界向内收缩1，表示已打印，如果边界相遇说明打印已完成。

首先在第一行开始从左到右打印，打印完第一行之后，上边界下移，也就是top加一，然后从上边界开始从上到下打印，打印完后右边界左移，然后从右边界从右到左打印，下边界上移，然后从下边界从下到上打印，一直如此循环。

打印行的时候只需要看上边界是否大于下边界，如果大于就退出，表示打印完了；同样打印列的时候看左边界是否大于右边界，大于就退出。

模拟过程：

假设矩阵是 3行3列：

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

初始：l=0, r=2, t=0, b=2

第一轮循环：

1. 从左到右：res.append(matrix[0][0..2])→ [1,2,3]

2. t += 1→ t=1

3. 从上到下：res.append(matrix[1..2][2])→ [1,2,3,6,9]

4. r -= 1→ r=1

5. 从右到左：res.append(matrix[2][1..0])→ [1,2,3,6,9,8,7]

6. b -= 1→ b=1

7. 从下到上：res.append(matrix[1..0][0])→ [1,2,3,6,9,8,7,4]

8. l += 1→ l=1

此时边界：l=1, r=1, t=1, b=1

第二轮循环开始：

1. 从左到右：res.append(matrix[1][1..1])→ [1,2,3,6,9,8,7,4,5]

2. t += 1→ t=2

3. 检查 if t > b: break

   • 现在 t=2, b=1

   • 2 > 1成立 ✅

   • break 退出循环

48. 旋转图像（中等）

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

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

示例 1：

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

示例 2：

输入：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]]

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n=len(matrix)
        for i in range(1,n):
            for j in range(i):
                matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
        for row in matrix:
            row.reverse()

顺时针旋转90度就是转置+水平镜像也就是左右翻转

逆时针旋转90度就是转置+垂直镜像也就是上下翻转

180度旋转就是水平镜像+垂直镜像

reverse函数是指对数字内每一行进行原地反转。

如果不用函数，上下翻转和左右翻转代码如下：

#上下翻转
for i in range(n//2):
    metrix[i],metrix[n-1-i]=metrix[n-1-i],metrix[i]

#左右翻转
for i in range(n):
    for j in range(n//2):
        metrix[i][j],metrix[i][n-1-j]=metrix[i][n-1-j],metrix[i][j]

n//2是n除以2然后向下取整。

240. 搜索二维矩阵 II（中等）

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：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

示例 2：

输入：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 = 20
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -109 <= target <= 109

最无脑的暴力解：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m=len(matrix)
        n=len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j]==target: return True
        return False

就是直接遍历全矩阵，找到返回true，没找到返回false。

最优解：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)  # 行数
        n = len(matrix[0])  # 列数
        
        i, j = 0, n-1  # 从右上角开始
        
        while i < m and j >= 0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] < target:
                i += 1  # 当前行太小，下移
            else:
                j -= 1  # 当前列太大，左移
        
        return False

从右上角开始遍历矩阵，因为右边一列就是每一行中最大的数。如果最右边那一列的值比目标值小，那么下移找更大的，如果大那么左移找更小的。

• 时间复杂度：O(m+n)，不是 O(mn)

• 空间复杂度：O(1)

• 最坏情况：从右上角到左下角，走 m+n-1 步