哈希

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

1
2
3
4
5
6
7
#穷举
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1,n):
                if nums[i] + nums[j] == target: return [i,j]
1
2
3
4
5
6
7
#哈希表
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        mp = {}
        for i,num in enumerate(nums):
            if num in mp: return [mp[num],i]
            else: mp[target-num] = i

49. 字母异位词分组

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

1
2
3
4
5
6
7
8
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = {}
        for s in strs:
            tmp = ''.join(sorted(s))
            if tmp in mp: mp[tmp] += [s]
            else: mp[tmp] = [s]  
        return list(mp.values())
1
2
3
4
5
6
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list) #使用defaultdict给没有定义的key一个默认value：None
        for s in strs:
            d[''.join(sorted(s))].append(s)  # sorted(s) 相同的字符串分到同一组
        return list(d.values())

128. 最长连续序列

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#集合作哈希表
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        res = 0
        nums_set = set(nums) #set集合也是哈希表
        for n in nums_set:
            if n-1 not in nums_set:
                cur_num = n
                cur_res = 1            
                while cur_num+1 in nums_set:
                    cur_num += 1
                    cur_res += 1
                res = max(res,cur_res)       
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        res = 0
        hash_dict = dict()
        for num in nums:
            # 新进来哈希表一个数
            if num not in hash_dict:
                # 获取当前数的最左边连续长度,没有的话就更新为0
                left = hash_dict.get(num-1,0)
                # 同理获取右边的数
                right = hash_dict.get(num+1,0)           
                # 更新长度
                length = left+1+right
                res = max(res,length)
                # 更新当前和左右端点的值
                hash_dict[num] = length
                hash_dict[num-left] = length
                hash_dict[num+right] = length
                # 此时 []num-left，num-right]范围的值都连续存在哈希表中了
        return res

双指针

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

1
2
3
4
5
6
7
8
9
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        n = len(nums)
        i = j = 0
        while j < n :
            if nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
            j += 1

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        l, r = 0, n-1
        res = 0
        while l < r:
            if height[l] <= height[r]:
                res = max(res, (r-l)*height[l])
                l += 1
            else: 
                res = max(res, (r-l)*height[r])
                r -= 1
        return res

15. 三数之和

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

你返回所有和为 0 且不重复的三元组。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        nums.sort()
        for k in range(n-2):
            if nums[k] > 0: break
            if k > 0 and nums[k] == nums[k-1]: continue
            i, j = k+1, n-1
            while i < j:
                s = nums[k] + nums[i] + nums[j]
                if s > 0: 
                    j -= 1
                    while i < j and nums[j] == nums[j+1]: j -= 1
                elif s < 0: 
                    i += 1
                    while i < j and nums[i] == nums[i-1]: i += 1
                else: 
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[j] == nums[j+1]: j -= 1
                    while i < j and nums[i] == nums[i-1]: i += 1
        return res

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#动态规划
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        leftmax = [0] * n
        rightmax = [0] * n
        leftmax[0], rightmax[-1] = height[0], height[-1]
        for i in range(1,n):
            j = -i -1
            leftmax[i] = max(leftmax[i-1], height[i])
            rightmax[j] = max(rightmax[j+1], height[j])
        res = 0
        for i in range(n):
            res += min(leftmax[i],rightmax[i]) - height[i]
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#双指针dp
class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        n = len(height)
        l, r = 0, n-1
        lm = rm = 0
        while l < r:
            lm = max(lm, height[l])
            rm = max(rm, height[r])
            if lm < rm:
                res += lm - height[l]
                l += 1
            else:
                res += rm - height[r]
                r -= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#单调栈
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        stk = []
        res = 0
        for i,h in enumerate(height):
            while stk and h > height[stk[-1]]:
                d = stk.pop()
                if not stk: break
                l = stk[-1]
                res += (i-l-1)*(min(height[l],h) - height[d])
            stk.append(i)
        return res