438. 找到字符串中所有字母异位词
笨方法，划定一个长度为 m m m的窗口，在字符串 s s s上进行滑动，每次都对窗口内的字串进行排序，和排序后的 p p p进行比较 。复杂度很高 。为 O ( n m l o g ( m ) ) O(nmlog(m)) O(nmlog(m)) 。其中 n n n为 s s s的长度，m m m为 p p p的长度 。勉强AC 。
class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:m, n = len(p), len(s)res = []sorted_p = sorted(p)for i in range(n-m+1):if sorted(s[i:i+m]) == sorted_p:res.append(i)return res
那么自然会想到还有一种字典的方法 。
class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:m, n = len(p), len(s)res = []counter_p = Counter(p)for i in range(n-m+1):if Counter(s[i:i+m]) == counter_p:res.append(i)return res
没想到的是，这个提交上去不仅速度一样慢，空间占用也很多 。
那么，还有其他更快的方法吗？肯定是有的 。
上面的两种做法有一个问题就是对每一个窗口都需要重新排序或者统计字母的频率，很容易想到这里面有重复计算 。因为相邻两个窗口其实后一个只是在前一个窗口的基础上去掉了第一个，追加了之前窗口的后一个，那么每次只需要更新这两个就行了其实 。
class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:m, n = len(p), len(s)if m > n:return []res = []p_count = [0] * 26s_count = [0] * 26# 先对第一个窗口进行处理for i in range(m):p_count[ord(p[i]) - 97] += 1s_count[ord(s[i]) - 97] += 1if p_count == s_count:res.append(0)# 往后遍历for i in range(1, n-m+1):s_count[ord(s[i-1]) - 97] -= 1s_count[ord(s[i+m-1]) - 97 ] += 1if s_count == p_count:res.append(i)return res
543. 二叉树的直径Easy
经过一个节点 n o d e node node的最长路径和是：左子树最大深度加上右子树最大深度再加1 。在求树的最大深度时，也会递归求每一个节点左子树和右子树的最大深度，所以只需要在求树的最大深度基础上进行一下修改 。每次递归的时候都求一下当前最大路径 。
# Definition for a binary tree node.# class TreeNode:#def __init__(self, val=0, left=None, right=None):#self.val = val#self.left = left#self.right = rightclass Solution:def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:self.res = 0def dfs(root):if not root: return 0L = dfs(root.left)R = dfs(root.right)self.res = max(self.res, L + R + 1)return max(L, R) + 1dfs(root)return self.res - 1
238. 除自身以外数组的乘积
这一题主要难在两个额外的要求上，不能使用除法，必须在 O ( n ) O(n) O(n)的复杂度以内 。
方法就是，两次遍历数组 。维护一个全为1的数组 r e s res res，每次遍历到 i i i，都记录 i i i左边的所有数的乘积，然后让 r e s [ i ] res[i] res[i]乘上去 。这样一来，r e s res res中每个数都是它在 n u m s nums nums中对应位置的左边的数的乘积 。第二次便利的时候，记录每一个数右边的所有数的乘积，然后每个数乘 。两次遍历就行了 。
为了更简化，可以在一次遍历的时候直接把左右两边都算了 。
class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:# 方法就是，记录每一个数字左边所有数字的积，记录每一个数字右边数字的积 。# 然后每一个数字左边的积乘上右边的积即可 。left_times = 1right_times = 1n = len(nums)res = [1] * nfor i in range(n):# 从左到右乘左边的数之积res[i] *= left_timesleft_times *= nums[i]# 从右到左res[n - i - 1] *= right_timesright_times *= nums[n - i - 1] return res