数组

1. Two Sum

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = dict()
        for idx, num in enumerate(nums):
            if target - num in dic:
                return [idx, dic[target - num]]
            dic[num] = idx
        return [-1, -1]

• 时间复杂度：
• 空间复杂度：

167. Two Sum II - Input Array Is Sorted

原数组是非严格单调递增，要求使用常数的空间。
利用数组的有序性，双指针不断缩减搜索空间，每次去掉一行或一列。 =>

• 对角线：l == r
• 下三角：l > r; 上三角：l < r

类似思想的题目还有：

• 11. Container With Most Water
• 240. Search a 2D Matrix II

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        l, r = 0, len(nums) - 1
        while l < r:
            sum_two = nums[l] + nums[r]
            if sum_two < target:
                l += 1
            elif sum_two > target:
                r -= 1
            else:
                return [l+1, r+1]
        return [-1, -1]

• 时间复杂度：
• 空间复杂度：

170. Two Sum III - Data structure design

数据结构设计题，其中add(num)的调用次数远大于find(value)。
Approach I
转化为有序数组，利用双指针查找。其中排序环节设定在调用次数较少的find()。
使用一个类变量self.is_sorted来记录当前数组是否有序。

class TwoSum:

    def __init__(self):
        self.nums = []
        self.is_sorted = False

    def add(self, num: int) -> None:
        self.nums.append(num)
        self.is_sorted = False

    def find(self, value: int) -> bool:
        if not self.is_sorted:
            self.nums.sort()
            self.is_sorted = True

        l, r = 0, len(self.nums) - 1
        while l < r:
            sum_two = self.nums[l] + self.nums[r]
            if sum_two < value:
                l += 1
            elif sum_two > value:
                r -= 1
            else:
                return True

        return False

• 时间复杂度：其中add()，find()
• 空间复杂度：

Approach II （更优的解法）
使用字典记录每个数字出现的频次，注意遍历字典时分情况讨论：两个数字是否相等。

from collections import defaultdict

class TwoSum:

    def __init__(self):
        self.dic = defaultdict(int)        # 存储每一个num对应的出现频次

    def add(self, num: int) -> None:
        self.dic[num] += 1

    def find(self, value: int) -> bool:
        for num1 in self.dic.keys():
            num2 = value - num1
            if num1 == num2:
                if self.dic[num1] >= 2:    # 相同的数需要出现至少两次
                    return True
            else:
                if num2 in self.dic:
                    return True

        return False

• 时间复杂度：其中add()，find()
• 空间复杂度：

48. Rotate Image

要求使用常数空间。

对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。

首先考虑使用辅助数组，再复制回原数组。
Approach I
连续四次带入上式，得到4个转移方程。

class Solution:
    def rotate(self, A: List[List[int]]) -> None:
        n = len(A)
        for i in range(n // 2):
            for j in range((n+1) // 2):
                A[j][n-1-i], A[n-1-i][n-1-j], A[n-1-j][i], A[i][j] = \
                A[i][j], A[j][n-1-i], A[n-1-i][n-1-j], A[n-1-j][i]

• 时间复杂度：
• 空间复杂度：

Approach II

class Solution:
    def rotate(self, A: List[List[int]]) -> None:
        n = len(A)

        for i in range(n // 2):
            for j in range(n):
                A[i][j], A[n-1-i][j] = A[n-1-i][j], A[i][j]

        for i in range(n):
            for j in range(i):
                A[i][j], A[j][i] = A[j][i], A[i][j]

• 时间复杂度：
• 空间复杂度：

41. First Missing Positive

**原地哈希**：将数值为的数映射到下标为的位置。
考虑极端情况，数组长度为，其中包含了所有的数字，那么第一个缺失的正数便是。
我们用数组的索引作为引导，遍历中不断交换使得，建立一一对应关系。

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

        for i, num in enumerate(nums):
            if num != i + 1:
                return i + 1
        return n + 1

• 时间复杂度：
• 空间复杂度：

剑指 Offer 03. 数组中重复的数字

442. Find All Duplicates in an Array

448. Find All Numbers Disappeared in an Array

49. Group Anagrams

Approach I 排序
sorted会将str转为list

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = collections.defaultdict(list)
        for s in strs:
            dic[''.join(sorted(s))].append(s)
        return list(dic.values())

• 时间复杂度：，遍历个字符串，每个字符串排序需要的时间，更新哈希表的时间为
• 空间复杂度：，是字符串数量，是字符串最大长度

Approach II 计数
dic的key不能使用list，需要转成tuple

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = collections.defaultdict(list)
        for s in strs:
            cnts = [0] * 26
            for c in s:
                cnts[ord(c) - ord('a')] += 1
            dic[tuple(cnts)].append(s)
        return list(dic.values())

• 时间复杂度：，遍历个字符串，每个字符串需要的时间计算每个字母的频数，再使用的时间生成哈希表的key
• 空间复杂度：，是字符串数量，是字符串最大长度

169. Majority Element

思路：对拼消耗

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majo, cnt = None, 0
        for num in nums:
            if cnt == 0:
                majo = num
            cnt += 1 if majo == num else -1
        return majo

• 时间复杂度：
• 空间复杂度：

1013. Partition Array Into Three Parts With Equal Sum

238. Product of Array Except Self

54. Spiral Matrix

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        up, down, left, right = 0, m - 1, 0, n - 1  # 上下左右边界，不断收窄
        res = []

        while 1 == 1:
            for j in range(left, right + 1):        # 向右
                res.append(matrix[up][j])
            up += 1
            if up > down:
                break

            for i in range(up, down + 1):           # 向下
                res.append(matrix[i][right])
            right -= 1
            if left > right:
                break

            for j in range(right, left - 1, -1):    # 向左
                res.append(matrix[down][j])
            down -= 1
            if up > down:
                break

            for i in range(down, up - 1, -1):       # 向上
                res.append(matrix[i][left])
            left += 1
            if left > right:
                break

        return res

• 时间复杂度：
• 空间复杂度：

128. Longest Consecutive Sequence

73. Set Matrix Zeroes

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        row_flags = [False] * m
        col_flags = [False] * n

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row_flags[i] = col_flags[j] = True

        for i in range(m):
            for j in range(n):
                if row_flags[i] or col_flags[j]:
                    matrix[i][j] = 0

• 时间复杂度：
• 空间复杂度：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        row_flag = col_flag = False  # 记录首行首列

        for i in range(m):
            if matrix[i][0] == 0:
                row_flag = True
                break

        for j in range(n):
            if matrix[0][j] == 0:
                col_flag = True
                break

        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][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_flag:
            for i in range(m):
                matrix[i][0] = 0

        if col_flag:
            for j in range(n):
                matrix[0][j] = 0

• 时间复杂度：
• 空间复杂度：