二刷力扣--哈希表

哈希表

哈希表可以根据键在O(1)时间内进行访问。
哈希表实际上可以看成是一个数组，但是可以通过哈希函数计算出数组下标，直接访问。

常用的有集合set()，字典dict()。

有效的字母异位词 242.

#字典
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

1. 使用数组

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26
        for i in s:
            #并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            record[ord(i) - ord("a")] += 1
        for i in t:
            record[ord(i) - ord("a")] -= 1
        return  all(x == False for x in record)
1
2
3
4
5
6
7
8
9

2. 使用字典

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        from collections import defaultdict
        s_dict = defaultdict(int)
        t_dict = defaultdict(int)
        for x in s:
            s_dict[x] += 1
        for x in t:
            t_dict[x] += 1
        return s_dict == t_dict
1
2
3
4
5
6
7
8
9
10

Python还提供了一个默认的计数器Counter，效果和上面一样。

class Solution(object):
    def isAnagram(self, s: str, t: str) -> bool:
        from collections import Counter
        return Counter(s) == Counter(t)
1
2
3
4

两个数组的交集 349.

#集合
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。
Python 的set实现了集合运算，直接转换成集合然后求交。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set_1 = set(nums1)
        set_2 = set(nums2)
        return  list(set_1 & set_2)
1
2
3
4
5

快乐数 202.

#集合
编写一个算法来判断一个数 n 是不是快乐数。

使用集合来判断n有没有出现过。

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_sum(num):
            s = 0
            while num:     
                s +=  (num % 10)** 2
                num =  num // 10
            return s
        
        visited = set()
        while n != 1 and  not n in visited:
            visited.add(n)
            n = get_sum(n)

        return  n == 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

除了正常的取余获得num各位数字，还可以用字符串：

n = sum(int(i) ** 2 for i in str(n))
1

两数之和 1.

#字典
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
容易想到用暴力循环来两两匹配，时间复杂度为O(N^2)。但是学完字典后，可以想到用字典存储出现过的数字及下标。 遍历过程中可以查看字典中是否有能组成target的数。时间复杂度为O(N)。
（也可以用集合存储数字，但是还需要找一次下标）

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = dict()
        for i,n in enumerate(nums):
            if target-n in d:
                return i, d[target-n]
            else:
                 d[n] = i
1
2
3
4
5
6
7
8

四数相加II 454.

#字典
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

两数相加的扩展版。
从四个数组中各取一个数，和为0。
容易想到将四数相加变成两数相加。这样就将4重循环变成2重循环。
nums1 + nums2 = -(nums3 + nums4)

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        d = defaultdict(int)
        for i in nums1:
            for j in nums2:
                d[i+j]  += 1
        count  = 0 
        for k in nums3:
            for l in nums4:
                count += d[-(k+l)]
        return count
1
2
3
4
5
6
7
8
9
10
11

赎金信 383.

#字典
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

和 有效的字母异位词有点像，但是这里只要magazine中字符数量大于ransomNote。

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        d_ransomNote = Counter(ransomNote)
        d_magazine = Counter(magazine)
        for k,v in d_ransomNote.items():
            if k not in d_magazine or d_magazine[k] < v:
                return False
        return True

1
2
3
4
5
6
7
8
9

三数之和 15.

#字典 #双指针
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。
可以用字典做，两重循环确定num[i]和nums[j]，然后用字典确定是否有nums[k] == -(nums[i]+ nums[j])。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        d = defaultdict(list)
        for i,n in enumerate(nums):
            d[n].append(i)
        res = set()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if  -(nums[i] + nums[j]) in d and d[-(nums[i] + nums[j])] != [i] \
                and d[-(nums[i] + nums[j])] != [j]  and d[-(nums[i] + nums[j])] != [i,j]:
                    res.add(tuple(sorted([nums[i], nums[j],-(nums[i] + nums[j]) ])))

        return [list(t) for t in res]
1
2
3
4
5
6
7
8
9
10
11
12
13

双指针：
需要先对nums排序。
固定i后，用指针left和right找剩余的两个数。
（这里我去重直接用了set，没有像网站那样额外判断。）

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = set()
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left = i+1
            right = len(nums) - 1
            while right > left:
                s = nums[i] + nums[left] + nums[right]
                if s < 0:
                    left += 1
                elif s > 0:
                    right -= 1
                else:
                    res.add((nums[i], nums[left], nums[right]))

                    right -= 1
                    left += 1
        return  [list(t)  for t in res]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

四数之和 18.

#双指针
在三数之和的基础上再套一层for循环。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:   
        nums.sort()
        res  = set()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                left = j+1
                right = len(nums) - 1
                
                while left < right:
                    s = nums[i]+nums[j] + nums[left] + nums[right]
                    if s < target:
                        left += 1
                    elif s > target:
                        right -= 1
                    else:
                        res.add((nums[i],nums[j] , nums[left] , nums[right]))
                        left += 1
                        right -= 1

        return  [list(t)  for t in res]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

哈希表小结

哈西表常用来判断元素是否出现过，统计出现次数，去重。
本章题目大多数和数组相关，用到了对数组排序、双指针的方法。