总结

题目总结

1-001-两数之和

leetcode-001

• 输入数组nums和目标值target，求解和为target的两个整数下标。

暴力法：依次遍历

补数Hash查找法

• hash存储已遍历数字位置；
• 求解当前数的补数；如果补数已遍历，则成功；如果没遍历，则存储。

2-049-字母异位词分组

leetcode-049

• 给多个字符串，求解里面字符相同 (字母异位词)的字符串，构建list元素，

字符串生成key做分组

• 每个字符串，生成一个key，按key分组。key：直接字符串排序即可。

3-128-最长连续序列

leetcode-128

• 给一个未排序的整数数组，输出最长的 连续数字序列长度。

排序遍历判断数字连续法

• 先对数组进行从小到大排序，再依次遍历，
• 判断当前数字是否比前面的大1，更新最大长度

数组去重判断起点往后找法

• 先对数组去重，构建元素集合
• 遍历，判断当前num是否为起点：
  • 如果是起点：则开子循环，继续找后面的数，更新长度；
  • 如果不是起点：则跳过。

题目

1-001-两数之和

1-001-两数之和

leetcode-001

• 输入：数组nums、目标值target。
• 输出：和为目标值的两个整数下标。

相似题

• 001-两数之和
• 015-三数之和
• 560-和为K的子数组
• 053-最大子数组和

暴力法：依次遍历

笔记

• 固定一个数字，从前往后暴力遍历另外一个数字

def twoSum_loop(self, nums: List[int], target: int) -> List[int]:
    """ 暴力解法
    """
    for i, a in enumerate(nums):
        # 注意遍历
        for j in range(i+1, len(nums)):  
            b = nums[j]
            if a + b == target:
                return [i, j]  
    return [0, 1]

补数Hash查找法

补数Hash查找法

• 使用hash，存在已遍历过数字的位置
• 每遍历一个数字num，计算求和为target的补数
• 补数若出现过：则返回当前位置和补数位置即可。
• 补数没出现过：则存储当前数字

def twoSum_hash(self, nums: List[int], target: int) -> List[int]:
    """ 记录已遍历的数字，循环数字，查看需要的是否存在
    """
    # 1. 已经遍历过数字的位置
    num2index = {}
    for index, num in enumerate(nums):
        # 2. 固定当前数字，需要的另一个数字
        complement = target - num  
        if complement in num2index:  
            # 存在则返回
            return [index, num2index[complement]]
        else:
            # 不存在，则存入当前num
            num2index[num] = index
    return [0, 1]

2-049-字母异位词分组

2-049-字母异位词分组

leetcode-049

• 输入：多个字符串组成的数组。["abc", "cba", "aaa"]
• 输出：把字母异位词相同字符串放在一起，组成新的元素，返回新元素组成的数组
  • [["abc", "cba"], ["aaa"]]

字母异位字符串

• 组成的字符相同，仅是位置不同。
• 如 abc和cba为异位词，aaa和abc 则不是。

相关题目

• 滑动窗口-2-438-找到字符串中所有字母异位词

字符串生成key做分组

字符串生成key做分组

• 为每个字符串，生成一个key，按key分组。
• key：字符排序，从小到大。保证 abc 和 cba 的key相同即可。

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    """排序后的字符串是一样的，作为hash表的key，把key相同的字符串放在一起
    """
    group_list = []
    # 字符串key
    key2strs = {}  
    for raw_str in strs:
        # 注意这个sorted方法，直接可以对字符串做排序，返回char str数组
        sorted_chars = sorted(raw_str)  
        key = "".join(sorted_chars)
        if key not in key2strs:
            key2strs[key] = []
        key2strs[key].append(raw_str) 
    for key, str_list in key2strs.items():  
        group_list.append(str_list)
    return group_list

3-128-最长连续序列

3-128-最长连续序列

leetcode-128

• 输入：一个未排序的整数数组
• 输出：数组中各元素组成的，最长连续序列的长度。
• 示例：
  • [100,4,200,1,3,2]，最长连续是 [1,2,3,4]，输出4
  • 连续：整数连续

排序遍历判断数字连续法

排序遍历判断数字连续法

• 先对数组进行排序
• 排序后依次遍历
  • 判断当前数字是否和上一个数连续，相差为1；
    • 若连续：长度+1
    • 不连续：长度清0，更新最大长度

def longestConsecutive_sort(self, nums: List[int]) -> int:
    if len(nums) < 2:
        return len(nums)
    # sorted_nums = sorted(nums)
    # 对nums做排序
    nums.sort()

    max_length = 1
    cur_length = 1
    for i in range(1, len(nums)):
        # 两个数相同，则跳过
        if nums[i] == nums[i-1]:  
            continue

        # 当前数和上一个数连续，就继续+1
        if nums[i] == nums[i-1] + 1:  
            cur_length += 1
        else:
            # 当前数和上一个数不连续
            max_length = max(cur_length, max_length)
            cur_length = 1
    max_length = max(cur_length, max_length)
    return max_length

数组去重起点判断往后找法

数组去重起点判断往后找法

• 先对数字去重，存入hash表。
• 找序列的起点，遍历每个num，判断其是否为起点。
  • 如果num-1不存在，则num为起点。
    • 开启子循环，从num开始往后数(num+1, num+2, ..)
    • 更新最大长度
  • 如果num-1存在，则num不是起点，跳过num，等到真正的起点再开始找。
• 最终返回最大长度

def longestConsecutive_hash(self, nums: List[int]) -> int:
    """ 做hash，循环nums，判读num是否为起点，若为起点再开始往后找
    """
    if not nums:
        return 0

    # 1. 数组去重，做hash，方便判断是否存在
    num_set = set(nums)  
    max_length = 1
    # 2. 循环判断num，是否为起点
    for num in num_set:
        if num-1 in num_set:  
            # num 不为起点，跳过
            continue 
        else:
            # 3. num为起点，单开子循环，继续往后找
            next_num = num + 1
            cur_length = 1
            # 一直往后找
            while next_num in num_set:  
                next_num += 1
                cur_length += 1
            max_length = max(max_length, cur_length)  
    return max_length