数组常用想法总结：
（以下默认 nums为数组。）
1.遍历数组
遍历：
for num in nums:
xxxx
带索引遍历
for idx,num in enumerate(nums):
xxxx
2.动态规划(dp)
动态规划一般可以用一个数组保存状态。见 53.最大子数组和。
用数组保存状态是非常常用的做法。例如 36.有效的数独、 73. 矩阵置零。
3.双指针
见 88.合并两个有序数组、350.两个数组的交集 II
可以是左右指针对一个数组使用。
也可以是两个指针遍历两个数组。
while index1<m and index2<n:
列表常用函数
Python中一般用 list实现可变数组。
下面是 list常用的函数。
（可变序列类型通用操作，只有 .sort是 list独有的。参考序列操作文档）
| 函数 | 功能 |
|---|---|
nums.sort(key,reversed) |
（原地）按照key升序排序，reversed可以指定是否反转。 |
sorted(nums,key,reversed) |
用法与 nums.sort类似，但返回另一个数组，原数组不变。 |
s.append(x) |
将 x 添加到序列的末尾 |
s.extend(t)或 s += t |
用 t 的内容扩展 s |
x in s |
判断x是否在数组 nums中。 |
len(s) |
返回 s长度 |
max(s)、min(s) |
返回 s最大值、最小值 |
all(iterable) |
如果 iterable的所有元素均为真值（或可迭代对象为空）则返回 True |
any(iterable) |
如果 iterable的任一元素为真值则返回 True。 如果可迭代对象为空，返回 False。 |
多维列表的一个坑
创建多维列表，一般用
w, h = 2, 3
A = [[None] * w for i in range(h)]
等价于
A = [None] * 3
for i in range(3):
A[i] = [None] * 2
而不是
A = [[None] * 2] * 3
原因在于用 *对列表执行重复操作并 不会创建副本 ，而只是创建现有对象的 引用 。 *3创建的是包含 3 个引用的列表，每个引用指向的是同一个长度为 2 的列表。
如果你给一项赋值，就会发现这个问题：
>>> A[0][0] = 5
>>> A
[[5, None], [5, None], [5, None]]
第1天
217. 存在重复元素
给定数组，判断是否存在重复元素。
做法：
- 直接遍历（穷举）
- 排序后，比较每个元素和下一个元素
- 哈希表
直接遍历会超时。
2的时间复杂度是O(nlogn) 也就是排序的时间复杂度
3的时间复杂度是O(n)，但需要额外的O(n)辅助空间。
（穷举法基本都能想到，但很容易超时，后面只有在穷举法能通过时才列出来。）
3比较简单，这里写一下3的做法：
return len(nums) != len(set(nums))
53. 最大子数组和
给定数组，求其中一个连续数组和的最大值。
比较容易想到的是用一个数组记录目前位置最大的值（动态规划）。
用 dp[i] 表示以 i位置结尾的连续数组和的最大值。
最后返回dp数组中最大值。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
length = len(nums)
dp = [0 for i in range(length)]
for i in range(length):
dp[i] = max(dp[i - 1], 0) + nums[i]
return max(dp)
题解给出了一种省略dp数组的方法：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
pre = 0
res = nums[0]
for x in nums:
pre = max(pre+x ,x)
res = max(res, pre)
return res
第2天
1. 两数之和
找出数组中两个数之和等于 target的两数下标。
暴力枚举可以
但时间较长，时间复杂度O(N^2)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
哈希表
官方题解的一个比较巧妙的方式：使用哈希表（字典）
用字典记录出现过的数字的位置。
时间复杂度O(N)，空间复杂度O(N)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []
88. 合并两个有序数组
两个有序数组，将第二个数组 nums2合并到第一个数组 nums1。
双指针
1.可以用双指针遍历两个数组：
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
# 两个中存在空数组的时，直接返回
if m == 0:
nums1[:] = nums2[:]
return
if n == 0:
return
index1,index2 = 0,0
t = []
while index1<m and index2<n:
if nums1[index1] <= nums2[index2]:
t.append(nums1[index1])
index1 += 1
else:
t.append(nums2[index2])
index2 += 1
if index1 < m:
t += nums1[index1:m]
else:
t += nums2[index2:n]
nums1[:] = t[:]
官方版本，更简洁、清楚。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
sorted = []
p1, p2 = 0, 0
while p1 < m or p2 < n:
if p1 == m:
sorted.append(nums2[p2])
p2 += 1
elif p2 == n:
sorted.append(nums1[p1])
p1 += 1
elif nums1[p1] < nums2[p2]:
sorted.append(nums1[p1])
p1 += 1
else:
sorted.append(nums2[p2])
p2 += 1
nums1[:] = sorted
（暴力） 追加后排序
- 更简单粗暴的方式是直接将
nums2追加到nums1后，进行排序。
及其简单而且效果很好。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
nums1[m:] = nums2
nums1.sort()
第3天
350. 两个数组的交集 II
以数组形式返回两数组的交集（数组形式，返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致）。
排序后双指针遍历。
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
i = 0
j = 0
result = []
while i<len(nums1) and j<len(nums2):
if(nums1[i]<nums2[j]):
i+=1
elif(nums1[i]>nums2[j]):
j+=1
else:
result.append(nums1[i])
i+=1
j+=1
return result
121. 买卖股票的最佳时机
只需要记录下当前最低价，遍历价格过程中，用当前价格-最低价 就是当前可获得的最大利润。另外如果出现了更低的价格，则最低价也要更新。（一个朴素的想法，要是我在最低点买进就好了）
总的最大利润就是这些利润中的最大值。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
r = 0
min_price = float('inf') # float('inf')表示正无穷
for price in prices:
min_price = min(min_price, price) # 截止到当前的最低价（买入价）
r = max(r, price - min_price) # 截止到目前的最高利润
return r
第4天
566. 重塑矩阵
给定一个 mxn的数组，重构为 rxc的数组。
比较简单的想法是把数组拉平为一位数组，然后逐个填充到新的数组中：
class Solution:
def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
m,n = len(mat), len(mat[0])
if m*n != r*c:
return mat
arr = []
for row in mat:
for x in row:
arr.append(x)
arr_index = 0
newmat = [[0 for j in range(c)]for i in range(r)]
for i in range(r):
for j in range(c):
newmat[i][j] = arr[arr_index]
arr_index += 1
return newmat
官方提供了一种直接计算下标的方法：
class Solution:
def matrixReshape(self, nums: List[List[int]], r: int, c: int) -> List[List[int]]:
m, n = len(nums), len(nums[0])
if m * n != r * c:
return nums
ans = [[0] * c for _ in range(r)]
for x in range(m * n):
ans[x // c][x % c] = nums[x // n][x % n]
return ans
118. 杨辉三角
找规律题。可以直接按照生成的规律生成数组。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = [[]for _ in range(numRows)]
res[0] = [1]
for i in range(1,numRows):
res[i].append(1)
for j in range(0,len(res[i-1])-1):
res[i].append(res[i-1][j] + res[i-1][j+1])
res[i].append(1)
return res
第5天
36. 有效的数独
判断当前数独是否有效（不需要填充数独）
只要用3个二维数组维护9行、9列、9个九宫格。
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row = [[] * 9 for _ in range(9)]
col = [[] * 9 for _ in range(9)]
nine = [[] * 9 for _ in range(9)]
for i in range(len(board)):
for j in range(len(board[0])):
tmp = board[i][j]
if not tmp.isdigit():
continue
if (tmp in row[i]) or (tmp in col[j]) or (tmp in nine[(j // 3) * 3 + (i // 3)]):
return False
row[i].append(tmp)
col[j].append(tmp)
nine[(j // 3) * 3 + (i // 3)].append(tmp)
return True
73. 矩阵置零
如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
A：
利用数组的首行和首列来记录 0 值
另外用两个布尔值记录首行首列是否需要置0
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
#标记
m,n = len(matrix), len(matrix[0])
row = any(x == 0 for x in matrix[0])
col = any(matrix[r][0] == 0 for r in range(m) )
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
#置零
for i in range(1,m):
for j in range(1,n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if row:
for j in range(0,n):
matrix[0][j] = 0
if col:
for i in range(0,m):
matrix[i][0] = 0
