class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums)
for i in range(length):
for j in range(i + 1, length):
if nums[i] + nums[j] == target:
return [i, j]- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
利用哈希表，时间复杂度 O(n)，空间复杂度 O(n)。
- 用 HashMap 存储数组元素和索引的映射
- 在访问到 nums[i] 时，判断 HashMap 中是否存在 target - nums[i]
- 如果存在说明：target - nums[i] 所在的索引和 i 就是要找的两个数
- 如果不存在：将 nums 加入 HashMap
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hash_dict = dict()
res_list = list()
for key, value in enumerate(nums):
other = target - value
if other in hash_dict:
res_list.append(hash_dict[other])
res_list.append(key)
break
else:
hash_dict[value] = key
return res_list2020.06.02 复盘：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
table = dict()
for i in range(len(nums)):
n = nums[i]
tmp = target - n
if tmp in table:
return [i, table[tmp]]
else:
table[n] = i题目要求 O(n) 复杂度。
- 用哈希表存储每个端点值对应连续区间的长度
- 若数已在哈希表中：跳过不做处理
- 若是新数加入：
- 取出其左右相邻数已有的连续区间长度 left 和 right
- 计算当前数的区间长度为：cur_length = left + right + 1
- 根据 cur_length 更新最大长度 max_length 的值
- 更新区间两端点的长度值
class Solution(object):
def longestConsecutive(self, nums):
hash_dict = dict()
max_length = 0
for num in nums:
if num not in hash_dict:
left = hash_dict.get(num - 1, 0)
right = hash_dict.get(num + 1, 0)
cur_length = 1 + left + right
if cur_length > max_length:
max_length = cur_length
hash_dict[num] = cur_length
hash_dict[num - left] = cur_length
hash_dict[num + right] = cur_length
return max_length用哈希表存了每个数出现的次数，果断超时。
class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
hash_dict = dict()
for num in nums:
if num in hash_dict:
hash_dict[num] = hash_dict[num] + 1
else:
hash_dict[num] = 1
max_length = 0
for key in hash_dict:
cur = key
count = 0
while cur in hash_dict:
count = count + 1
cur = cur + 1
if count > max_length:
max_length = count
return max_length双哈希表 + 双指针。
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
length1 = len(s)
length2 = len(t)
if length1 != length2:
return False
table1 = dict()
table2 = dict()
for i in range(length1):
if s[i] not in table1:
# 没有映射过
table1[s[i]] = t[i]
# 判断是否进行了相同映射
if t[i] in table2:
return False
table2[t[i]] = s[i]
else:
# 映射过了
if t[i] != table1[s[i]]:
# 映射的字母不同
return False
return True哈希表
class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
hash_map = dict()
for num in nums:
if num in hash_map:
return True
hash_map[num] = 1
return False也可以用 set，一样的
class Solution:
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
set1 = set(nums)
if len(set1) == len(nums):
return False
else:
return Trueclass Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))- 时间复杂度：将数组转为
set的复杂度为O(n)，转化两个数组时间复杂度O(m) + O(n)- 平均情况下：
O(m + n) - 最坏情况下：
O(m * n)
- 平均情况下：
- 空间复杂度：最坏情况
O(m + n)（数组元素都不同的情况）
先对二者排序，使用双指针滑动查找。
一个数组排序（短数组？），另一数组内的元素使用二分查找。
使用 hash 表的方式。
- 遍历较短数组，将数据存储在哈希表中，存储的值为数字出现的次数
- 遍历较长数组，查询数据是否在哈希表出现过
空间复杂度 O(n)，时间复杂度 O(n)。
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
hash_map = dict()
for n in nums1:
if n not in hash_map:
hash_map[n] = 1
else:
hash_map[n] = hash_map[n] + 1
res = list()
for n in nums2:
if n in hash_map and hash_map[n] != 0:
res.append(n)
hash_map[n] = hash_map[n] - 1
return res- 时间复杂度：
O(m + n) - 空间复杂度：
O(min(m, n))（不会超过短数组长度）
排序 + 双指针，不需要额外空间。
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
i = 0
j = 0
length1 = len(nums1)
length2 = len(nums2)
res = []
while i < length1 and j < length2:
if nums1[i] == nums2[j]:
res.append(nums1[i])
i += 1
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return res- 事件复杂度：
mO(logm) + nO(logn) - 空间复杂度：
O(len(res))（结果答案长度）
class Node:
def __init__(self, time, tweet_id, nxt):
"""
链表节点
"""
self.time = 0
self.nxt = nxt
self.tweet_id = tweet_id
class Twitter:
def __init__(self):
"""
Initialize your data structure here.
"""
self.time = 0
# 用户哈希
self.tweets = dict()
self.followers = dict()
def postTweet(self, userId: int, tweetId: int) -> None:
"""
Compose a new tweet.
"""
# node = Node(self.time, tweetId, None)
# if userId in self.tweets:
# head = self.tweet[userId]
# node.nxt = head
# self.tweets[userId] = node
# self.time += 1
if userId not in self.tweets:
self.tweets[userId] = []
self.tweets[userId].append([self.time, tweetId])
self.time += 1
def getNewsFeed(self, userId: int) -> List[int]:
"""
Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
"""
ans = []
# 取出关注的用户
followers = self.followers.get(userId, set())
# print(self.tweets)
tweets = []
if userId in self.tweets:
tweets = self.tweets[userId]
# print(tweets)
# print(followers)
for follower in followers:
# tweets.extend(self.tweets[follower])
if follower in self.tweets:
tweets = tweets + self.tweets[follower]
tweets.sort(key=lambda x: x[0], reverse=True)
# print(tweets)
# print(tweets)
# print([x[1] for x in tweets[:10]])
return [x[1] for x in tweets[:10]]
def follow(self, followerId: int, followeeId: int) -> None:
"""
Follower follows a followee. If the operation is invalid, it should be a no-op.
"""
if followerId == followeeId:
# 不允许自己关注自己
return
if followerId not in self.followers:
self.followers[followerId] = set()
self.followers[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
"""
Follower unfollows a followee. If the operation is invalid, it should be a no-op.
"""
if followerId not in self.followers:
return
self.followers[followerId].discard(followeeId)
# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)- 遍历
A和B所有元素和的组合情况，并记录在ab_map中，ab_map的key为两数和，value为该两数和出现的次数 - 遍历
C和D所有元素和的组合情况，取和的负值判断其是否在ab_map中，若存在则取出ab_map对应的value值，count = count + value
class Solution(object):
def fourSumCount(self, A, B, C, D):
"""
:type A: List[int]
:type B: List[int]
:type C: List[int]
:type D: List[int]
:rtype: int
"""
count = 0
ab_map = dict()
for a in A:
for b in B:
ab_map[a + b] = ab_map.get(a + b, 0) + 1
for c in C:
for d in D:
s = -(c + d)
if s in ab_map:
count += ab_map[s]
return count- 固定左边界
- 枚举右边界
func subarraySum(nums []int, k int) int {
length := len(nums)
ans := 0
for left := 0; left < length; left++ {
s := 0
for right := left; right < length; right++ {
s += nums[right]
if s == k {
ans += 1
}
}
}
return ans
}- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
用 pre[i] 表示 [0, ..., i] 的和。
因此，[j, ..., i] 的和为 k 可以表示为：pre[i] - pre[j - 1] == k。
移项后：pre[j - 1] == pre[i] - k，因此，只要统计 pre[i] - k 即可。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
ans, pre = 0, 0
nums_dict = dict()
nums_dict[0] = 1
for i in range(len(nums)):
pre += nums[i]
ans += nums_dict.get(pre - k, 0)
nums_dict[pre] = nums_dict.get(pre, 0) + 1
return ansfunc subarraySum(nums []int, k int) int {
length := len(nums)
pre := 0
ans := 0
m := map[int]int{}
m[0] = 1
for i := 0; i < length; i++ {
pre += nums[i]
if _, ok := m[pre - k]; ok {
ans += m[pre - k]
}
m[pre] += 1
}
return ans
}题目的意思是把所有的糖果分成两份，其中一份要尽可能拥有最多种类的糖果。
假设糖果一共有 x 颗，糖果种类有 y 种，那么分成两份后每份有糖果 x / 2：
- 如果
y >= x / 2，那么可以直接拿出x / 2种糖果 - 如果
y < x / 2，那么最多也只能分配到y种糖果了
所以这道题只要求出糖果的种类 y 即可。而求出糖果种类的方法也有好几种。
将糖果种类的数字值作为 key 存储在字典中，糖果一旦存在则进行标记，并将糖果种类加一。
class Solution:
def distributeCandies(self, candies: List[int]) -> int:
length = len(candies)
each = length // 2
type_dict = dict()
type_cnt = 0
for c in candies:
if type_dict.get(c, 0) == 0:
type_dict[c] = 1
type_cnt += 1
if type_cnt >= each:
return each
else:
return type_cntfunc distributeCandies(candies []int) int {
var candiesMap map[int]bool
candiesMap = make(map[int]bool)
var candiesCount = 0
for i := 0; i < len(candies); i++ {
candie := candies[i]
_, ok := candiesMap[candie]
// candie 不存在，开始计数
if !ok {
candiesMap[candie] = true
candiesCount += 1
}
}
var each = len(candies) / 2
if candiesCount >= each {
return each
} else {
return candiesCount
}
}class Solution {
public int distributeCandies(int[] candies) {
if (candies == null || candies.length <= 0) return 0;
Map<Integer, Integer> type = new HashMap<Integer, Integer>();
int typeCount = 0;
for (int i = 0; i < candies.length; i++) {
if (!type.containsKey(candies[i])) {
type.put(candies[i], 1);
typeCount++;
}
}
if (typeCount >= candies.length / 2) {
return candies.length / 2;
} else {
return typeCount;
}
}
}- 时间复杂度 O(n)
- 空间复杂度 O(n)
利用集合无重复元素的特性，将数据存入集合，从而求出糖果的种类。
class Solution:
def distributeCandies(self, candies: List[int]) -> int:
each = len(candies) // 2
candies_set = set(candies)
return each if each <= len(candies_set) else len(candies_set)- 时间复杂度 O(n)
- 空间复杂度 O(n)
先对数组进行排序，然后将相邻的数字进行对比，如果相邻数字不同，则说明出现了新种类的糖果。
class Solution:
def distributeCandies(self, candies: List[int]) -> int:
length = len(candies)
each = length // 2
candies.sort()
count = 1
for i in range(1, length):
if candies[i] != candies[i - 1]:
count += 1
return each if each <= count else countimport (
"sort"
)
func distributeCandies(candies []int) int {
var length = len(candies)
var each = length / 2
var count = 1
sort.Ints(candies)
for i := 1; i < length; i ++ {
if candies[i] != candies[i - 1] {
count++
}
}
if count >= each {
return each
} else {
return count
}
}- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
from collections import Counter
class Solution:
def distributeCandies(self, candies: List[int]) -> int:
each = len(candies) // 2
candies_count = len(Counter(candies))
return each if candies_count >= each else candies_count- 数值出现个数放入 hash 表
- 计算相差值为 1 的两个数出现的次数
class Solution(object):
def findLHS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
hash_dict = dict()
for num in nums:
if num in hash_dict:
hash_dict[num] = hash_dict[num] + 1
else:
hash_dict[num] = 1
max_length = 0
for key in hash_dict:
if key - 1 in hash_dict:
cur_length = hash_dict[key] + hash_dict[key - 1]
if cur_length > max_length:
max_length = cur_length
return max_lengthclass Solution:
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
table1 = dict()
table2 = dict()
length1 = len(list1)
length2 = len(list2)
for i in range(length1):
word = list1[i]
table1[word] = i
min_index = float('inf')
for j in range(length2):
word = list2[j]
if word in table1:
table2[word] = j + table1.get(word)
if table2[word] < min_index:
min_index = table2[word]
ans = []
for k, v in table2.items():
if v == min_index:
ans.append(k)
return ans使用哈希表实现。将文件内容作为哈希 key 值，文件路径数组作为 value。
使用 Go 语言的哈希 + 数组表示：contentMap := make(map[string][]string)。
import "strings"
func findDuplicate(paths []string) [][]string {
contentMap := make(map[string][]string)
ans := make([][]string, 0)
for _, pathString := range paths {
// 路径分割
paths := strings.Split(pathString, " ")
document := ""
for idx, path := range paths {
if idx == 0 {
document = path
} else {
// 按括号切分
contents := strings.Split(path, "(")
filePath := contents[0]
content := contents[1][:len(contents[1]) - 1]
fullPath := document + "/" + filePath
contentMap[content] = append(contentMap[content], fullPath)
}
}
}
for _, contents := range contentMap {
if len(contents) >= 2 {
ans = append(ans, contents)
}
}
return ans
}# 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 = right
class Solution:
def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
count = dict()
ans = list()
def collect(node):
if node is None:
return '#'
left_serial = collect(node.left)
right_serial = collect(node.right)
serial = "{},{},{}".format(node.val, left_serial, right_serial)
count[serial] = count.get(serial, 0) + 1
if count[serial] == 2:
ans.append(node)
return serial
collect(root)
return ans此题应当要用普通的数据结构实现哈希集合。
题目指出「所有的值都在 [0, 1000000] 的范围内」，因此我们可以设计 100 个桶，每个桶内容纳 10000 个值，正好可以容纳下所有的数据。
哈希函数的映射规则：hash_table[key % bucket][key // bucket]
class MyHashSet:
def __init__(self):
"""
Initialize your data structure here.
"""
# 给出 100 个桶
self.bucket = 100
# 桶内元素
self.bucket_num = 10000
# 初始化
self.hash_table = [[] for _ in range(self.bucket)]
def add(self, key: int) -> None:
if not self.hash_table[key % self.bucket]:
self.hash_table[key % self.bucket] = [0] * self.bucket_num
self.hash_table[key % self.bucket][key // self.bucket] = 1
def remove(self, key: int) -> None:
if self.hash_table[key % self.bucket]:
self.hash_table[key % self.bucket][key // self.bucket] = 0
def contains(self, key: int) -> bool:
"""
Returns true if this set contains the specified element
"""
if not self.hash_table[key % self.bucket]:
return False
return self.hash_table[key%self.bucket][key//self.bucket] == 1
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)- 哈希映射设计：如何通过
key找到合适的桶 - 哈希碰撞处理：许多
key都映射在一个桶里，如何进行这些值的存储与查找
class Bucket:
def __init__(self):
self.bucket = []
def put(self, key, value):
for i in range(len(self.bucket)):
k, v = self.bucket[i][0], self.bucket[i][1]
if k == key:
self.bucket[i] = (key, value)
return
self.bucket.append((key, value))
def get(self, key):
for i in range(len(self.bucket)):
k, v = self.bucket[i][0], self.bucket[i][1]
if k == key:
return v
return -1
def remove(self, key):
for i, kv in enumerate(self.bucket):
if key == kv[0]:
# 删除元素问题
del self.bucket[i]
class MyHashMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.bucket_count = 2069
self.hash_map = [Bucket() for _ in range(self.bucket_count)]
def put(self, key: int, value: int) -> None:
"""
value will always be non-negative.
"""
bucket_num = key % self.bucket_count
self.hash_map[bucket_num].put(key, value)
def get(self, key: int) -> int:
"""
Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
"""
bucket_num = key % self.bucket_count
return self.hash_map[bucket_num].get(key)
def remove(self, key: int) -> None:
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
"""
bucket_num = key % self.bucket_count
self.hash_map[bucket_num].remove(key)
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)使用哈希表存储 chars 中每个字符出现的次数，在遍历 words 时判断每个单词的字母是否可以命中 chars 的哈希表。
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
res = 0
word_dict = dict()
# 词汇统计
for c in chars:
if c not in word_dict:
word_dict[c] = 0
word_dict[c] += 1
# 开始拼写
for word in words:
tmp_word_dict = word_dict.copy()
get = True
for c in word:
if c in tmp_word_dict:
if tmp_word_dict[c] == 0:
get = False
break
else:
tmp_word_dict[c] -= 1
else:
get = False
break
if get:
res += len(word)
return resfunc countCharacters(words []string, chars string) int {
var res int
var wordMap = make(map[string]int)
// 统计 chars
for _, c := range chars {
if _, ok := wordMap[string(c)]; !ok {
// 不存在
wordMap[string(c)] = 0
}
wordMap[string(c)] += 1
}
// 统计 word 单词数，与统计比较
for _, word := range words {
everyWordMap := make(map[string]int)
for _, c := range word {
if _, ok := everyWordMap[string(c)]; !ok {
everyWordMap[string(c)] = 0
}
everyWordMap[string(c)] += 1
}
// 判断是否命中
get := true
for c, count := range everyWordMap {
if mapCount, ok := wordMap[string(c)]; ok {
// 存在
if count > mapCount {
get = false
break
}
} else {
get = false
break
}
}
if get {
res += len(word)
}
}
return res
}