leetcode - hot100 - python - 专题一：哈希

1、两数之和

• 简单

题目：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

• 示例 1：
  输入：nums = [2,7,11,15], target = 9
  输出：[0,1]
  解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
• 示例 2： 输入：nums = [3,2,4], target = 6 输出：[1,2]
• 示例 3： 输入：nums = [3,3], target = 6 输出：[0,1]

• 题解：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        self.nums=nums
        self.target=target
        for i in range(0,len(self.nums)-1):
            for j in range(i+1,len(self.nums)):
                if self.nums[i]+self.nums[j]==self.target:
                    return [i,j]

2、字母异位词分组

• 中等

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例

• 示例 1: 输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
• 示例 2: 输入: strs = [“”] 输出: [[“”]]
• 示例 3: 输入: strs = [“a”] 输出: [[“a”]]

• 题解

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        if len(strs)==1:
            return [strs]
        dict = {}
        for i in strs:
            ss=str(sorted(i))
            if ss not in dict:
                dict[ss]=[i]
            else:
                dict[ss].append(i)
        return list(dict.values())

3、最长连续序列

• 中等

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

• 示例 1： 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
• 示例 2： 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
• 示例 3： 输入：nums = [1,0,1,2] 输出：3

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res=set(nums) # 将 nums 转化为 set (去重,排序)
        rns=0 # 存储最大长度 
        for n in res:
            if n-1 not in res:
                length=1
                while n+1 in res:
                    length+=1
                    n+=1
                rns=max(length,rns)
        return rns


        # res=0
        # dic={} # 键代表num,值代表它的长度
        # for i in nums:
        #     if i not in dic:
        #         left=dic.get(i-1,0)
        #         right=dic.get(i+1,0)
        #         cur=left+1+right
        #         res=max(res,cur)
        #         dic[i]=cur
        #         dic[i-left]=cur
        #         dic[i+right]=cur
        # return res

# class Solution:
#     # def longestConsecutive(self, nums: List[int]) -> int:
#     def longestConsecutive(self, nums):
#         longest_streak = 0
#         num_set = set(nums)

#         for num in num_set:
#             if num - 1 not in num_set:
#                 current_num = num
#                 current_streak = 1

#                 while current_num + 1 in num_set:
#                     current_num += 1
#                     current_streak += 1

#                 longest_streak = max(longest_streak, current_streak)

#         return longest_streak