Leetcode-哈希表

136. 只出现一次的数字 https://leetcode-cn.com/problems/single-number/

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

解：

遍历数组，哈希表存。如果key在哈希表中，就直接pop出去，最后剩下的那个就是只出现一次的元素。

class Solution:

    def singleNumber(self, nums: List[int]) -> int:

        hashmap = dict()

        for num in nums:

            if num in hashmap:

                hashmap.pop(num)

            else:

                hashmap[num] = 1

        return hashmap.popitem()[0]

异或，a xor 0 == a； a xor a == 0；且满足交换律

class Solution:

    def singleNumber(self, nums: List[int]) -> int:

        res = 0

        for num in nums:

            res ^= num

        return res

242. 有效的字母异位词 https://leetcode-cn.com/problems/valid-anagram/

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。即字母一样但顺序不同。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

解：

对s和t进行排序，比较排序好的字符串。O(NlogN)

class Solution:

    def isAnagram(self, s: str, t: str) -> bool:

        return sorted(s) == sorted(t)

用hashmap来对字符串中的每个字母计数。O(N)

class Solution:

    def isAnagram(self, s: str, t: str) -> bool:

        def count_aph(s):

            aph_s = dict()

            for char in s:

                aph_s[char] = aph_s.get(char, 0) + 1   # 找不到key就返回0

            return aph_s

        aph_s = count_aph(s)

        aph_t = count_aph(t)

        if aph_s == aph_t:

            return True

        return False

1. 两数之和 https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

解：

暴力求解，遍历所有可能的第一个数，嵌套遍历第二个数。O(N²)，很可能超时

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        if nums is None or len(nums) <= 1 :

            return []

        n = len(nums)

        for i in range(n):

            for j in range(i+1, n):

                if nums[i] + nums[j] == target:

                    return [i, j]

        return []

哈希表，y = target - x，枚举x，查询 y。可以先遍历一遍同时存哈希表，再枚举x查询y。

也可以一边遍历存哈希表的时候立刻就查询。O(N)。

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        if nums is None or len(nums) <= 1 :

            return []

        n = len(nums)

        visited = dict()

        for i in range(n):

            visited[nums[i]] = i

        for i in range(n):

            y = target - nums[i]

            if y in visited and visited.get(y) != i:  # y在哈希表中且不重复利用同样的元素

                return [i, visited.get(y)]

        return []

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        if nums is None or len(nums) <= 1 :

            return []

        n = len(nums)

        visited = dict()

        for i in range(n):

            y = target - nums[i]

            if y in visited and visited.get(y) != i:

                return [visited.get(y), i]  # 这时候就是索引i在后了

            visited[nums[i]] = i

        return []

15. 三数之和 https://leetcode-cn.com/problems/3sum/

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ? 找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解：

暴力求解，三层嵌套，O(N³)，不写了。

x+y+z = target，枚举x、y，再去哈希表中查询target - x - y。O(N²)

关于下面代码存进哈希表的方法，进一步解释：

class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        if len(nums) < 3:

            return []

        res = set()

        nums.sort()

        n = len(nums)

        for i in range(n-2):

            if i > 0 and nums[i] == nums[i-1]:   # 去重

                continue

            # 退化为两数之和

            d = {}

            for y in nums[i+1:]:

                if not y in d:

                    d[0-nums[i]-y] = 1  # 如果y不在d中，就把0-x-y存入d中。这样如果某个y在d中，说明匹配的0-x-y一定已经在d中且位于y之前

                else:

                    res.add((nums[i], 0-nums[i]-y, y))

        return list(map(list, res))

sort & find，先排序O(NlogN)，枚举x作为第一个元素，在剩下的数组里去找y和z，即两边往中间夹。O(N²)，不需要额外空间。

class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        if len(nums) < 3:

            return []

        res = []

        nums.sort()

        n = len(nums)

        for i in range(n-2):

            if i > 0 and nums[i] == nums[i-1]:  # 去重，如果第一个数相同，跳过

                continue

            l, r = i+1, n-1

            while l < r:

                s = nums[i] + nums[l] + nums[r]

                if s < 0:

                    l += 1

                elif s > 0:

                    r -= 1

                else:

                    res.append((nums[i], nums[l], nums[r]))  # 记录解

                    # 去重，如果第二、第三个数相同，也跳过

                    while l < r and nums[l] == nums[l+1]:

                        l += 1

                    while l < r and nums[r] == nums[r-1]:

                        r -= 1

                    # 继续找可能的解

                    l += 1

                    r -= 1

        return res

18.四数之和 https://leetcode-cn.com/problems/4sum/

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

解：

和三数之和思路基本一致，固定两个数，去找后两个数。

class Solution:

    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:

        if len(nums) < 4:

            return []

        nums.sort()  # 先排序一下，便于判重

        res = set()

        n = len(nums)

        for i in range(n-3):

            if i >0 and nums[i] == nums[i-1]:

                continue

            for j in range(i+1, n-2):

                if j > i+1 and nums[j] == nums[j-1]:

                    continue

                d = {}

                for z in nums[j+1:]:

                    if not z in d:

                        d[target-nums[i]-nums[j]-z] = 1

                    else:

                        res.add((nums[i], nums[j], target-nums[i]-nums[j]-z, z))

        return list(map(list, res))

由于外层有两层嵌套，可以判重之后考虑做一下剪枝

class Solution:

    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:

        if len(nums) < 4:

            return []

        res = []

        nums.sort()

        n = len(nums)

        for i in range(n-3):

            if i > 0 and nums[i] == nums[i-1]:  # 去重，如果第一个数相同，跳过

                continue

            # 剪枝，如果当前的x与剩下最小三个数之和大于target 或 与最大三个数之和小于target，跳过

            if nums[i]+sum(nums[i+1:i+4]) > target or nums[i]+sum(nums[-3:]) < target:

                continue

            for j in range(i+1, n-2):

                if j > i+1 and nums[j] == nums[j-1]:  # 去重，如果第一个数相同，跳过

                    continue

                if nums[i]+nums[j]+sum(nums[j+1:j+3]) > target:

                    continue

                if nums[i]+nums[j]+sum(nums[-2:]) < target:

                    continue

                l, r = j+1, n-1

                while l < r:

                    s = target-nums[i]-nums[j]-nums[l]-nums[r]

                    if s < 0:   # 左右数之和大了

                        r -= 1

                    elif s > 0:

                        l += 1

                    else:

                        res.append((nums[i], nums[j], nums[l], nums[r]))  # 记录解

                        # 去重，如果第二、第三个数相同，也跳过

                        while l < r and nums[l] == nums[l+1]:

                            l += 1

                        while l < r and nums[r] == nums[r-1]:

                            r -= 1

                        # 继续找可能的解

                        l += 1

                        r -= 1

        return res

49.字母异位词分组 https://leetcode-cn.com/problems/group-anagrams/

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

解：

#242的扩展，注意dict是unhashable的，不能作为另一个字典的key，所以这里判断是否是异位词就用sorted。O(NKlogK)

class Solution:

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        if len(strs) <= 1:

            return [strs]

        words = dict()

        for s in strs:

            key = tuple(sorted(s))

            if not key in words:

                words[key] = [s]

            else:

                words[key].append(s)

        return list(words.values())

按小写字母计数的数组来判断是否是异位词，避免字典不能做key的问题。

class Solution:

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        if len(strs) <= 1:

            return [strs]

        words = dict()

        for s in strs:

            count = [0]*26

            for c in s:

                count[ord(c) - ord('a')] += 1  # 避免了字典不能哈希的问题

            key = tuple(count)

            if not key in words:

                words[key] = [s]

            else:

                words[key].append(s)

        return list(words.values())

3. 无重复字符的最长子串 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解：

双指针维护滑动窗口，定义字符到对应索引的映射来判断一个字符是否存在。当找到重复的字符时，窗口的左端更新到窗口中重复字符处，窗口从元素left+1到元素i。

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:

        if not s:

            return 0

        max_len = 0

        left = -1

        hashmap = dict()

        n = len(s)

        for i in range(n):

            if s[i] in hashmap:

                left = max(left, hashmap[s[i]])

            hashmap[s[i]] = i

            max_len = max(max_len, i-left)

        return max_len

同一个思路的另一种写法

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:

        if not s:

            return 0

        res = 0

        n = len(s)

        l, r = 0, 0

        window = dict()

        while r < n:

            char = s[r]

            window[char] = window.get(char, 0) + 1

            # 如果出现重复字符，就从最左边开始删除，一直删除到没有重复字符出现

            while window[char] > 1:

                char2 = s[l]

                window[char2] -= 1

                l += 1

            res = max(res, r-l+1)

            r += 1

        return res

巴特西

Leetcode-哈希表

最新文章

热门文章