两数之和

题目描述

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

解决思路

第一反应是将数字一个个相加再和target进行比较

但是这样耗时太多，根据题目的特性，这个题目只有一组解，也就是一遍就可以遍历出答案

先定义一个中间数res，res=target-num[i]

再对剩下的数字进行遍历比较就可以返回结果

代码实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            res = target-nums[i] 
            if res in nums[i+1:]:
                return [i,nums[i+1:].index(res)+i+1]

细节说明

表达式	含义
`nums[i:]`	从索引 `i` 开始，包含 `i`，取到最后。
`nums[i+1:]`	从 `i` 的下一个位置开始，取到最后。
`nums[:i]`	从开头开始取，取到索引 `i` 为止（不包含 `i`）。

.index() 是列表（List）的一个内置方法，它的功能是：在列表中寻找某个值，并返回它第一次出现的位置（索引）。

基本语法：

列表.index(要查找的值, 起始位置, 结束位置)

nums[i+1:].index(res)+i+1

因为nums[i+1] 会先切出一个新列表（剔除了当前元素及其之前的元素）。

返回的索引是新列表的索引，所以我们要加上原来的长度，i 从0开始取所以要加1

字母异位词分组

题目描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

解决思路

分组的依据是单词的组成字母能组成同一个单词，那么将单词的字母按照相同的规律进行排序那么组成的单词任然是一样的

代码实现

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        table={}
        for s in strs:
            s_ = "".join(sorted(s))
            if s_ not in table:
                table[s_] = [s]
            else:
                table[s_].append(s)
        return list(table.values())

细节说明

s_ = "".join(sorted(s))

拆开来写

char_list = sorted(s)      # 先排序，得到列表 ['a', 'e', 't']
s_ = "".join(char_list)    # 再拼合，得到字符串 "aet"

sorted(s) —— 拆解与排序

sorted() 是 Python 的内置函数，它可以接受任何序列。当你把字符串传给它时：

它会把字符串拆成一个个字符。
按照 Unicode 编码顺序（通常就是字母表顺序）进行升序排列。
关键点：它返回的是一个 列表（List），而不是字符串。

"".join(...) —— 缝合

join() 是字符串的方法。它的作用是把一个列表里的所有元素“粘”在一起，变成一个长字符串。

语法是："连接符".join(列表)

这里的连接符是 ""（空字符串），意味着字符之间不插入任何东西，直接头尾相接。

if s_ not in table:
    table[s_] = [s]   # 如果是第一次见这个组合，开辟一个新的分类列表
else:
    table[s_].append(s) # 如果已经有了，直接把原始字符串 s 塞进去

最长连续序列

题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解决思路

对于 nums 中的元素 x，以 x 为起点，不断查找下一个数 x+1,x+2,⋯ 是否在 nums 中，并统计序列的长度。

代码实现

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        st = set(nums)    #把nums转化为哈希集合
        m = len (st)
        ans=0
        for x in st:
            if x-1 in st:
                continue
            y=x+1
            while y in st:
                y += 1
            ans = max(ans,y-x)
            if ans * 2 >=m :
                break
        return ans