哈希表

time & space trade-off

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]

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

560. Subarray Sum Equals K

考虑以结尾的子数组的和，逆序遍历保证每个子数组的和都能在时间内求解。
Python使用此解法会TLE。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        num_subarray = 0
        for end in range(len(nums)):
            array_sum = 0             # 以end为结尾的子数组的和 --> nums[start:end+1]
            for start in range(end, -1, -1):
                array_sum += nums[start]
                if array_sum == k:
                    num_subarray += 1
        return num_subarray

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

上述方法可进行时间优化的地方在于，对于每个，能否在时间内找到相应的（或者说是找到相应的子数组数量）？当然，这需要引入额外的空间开销（哈希表）。

1. 定义是之前所有数字的和，则前缀和的公式:；
2. 假设子数组的和恰好等于，则有:；
3. 移项，得到:。

综上，考虑以结尾且和为的子数组数量，转化为求前缀和为的数量。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        freq = collections.defaultdict(int)
        freq[0] = 1
        array_sum = 0
        for num in nums:
            array_sum += num
            if array_sum - k in freq:
                count += freq[array_sum - k]
            freq[array_sum] += 1
        return count

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

1248. Count Number of Nice Subarrays

1512. Number of Good Pairs

若暴力枚举，时间复杂度

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        return sum(v*(v-1) // 2 for v in collections.Counter(nums).values() if v > 1)

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

128. Longest Consecutive Sequence

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        longest_len = 0
        for num in num_set:
            # 若num-1在集合中，不必重复计算
            if num - 1 not in num_set:
                current_num = num
                current_len = 1
                while current_num + 1 in num_set:
                    current_num += 1
                    current_len += 1
                longest_len = max(longest_len, current_len)
        return longest_len

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