哈希 & 双指针 & 滑动窗口

哈希

(1) twosum 题目返回数组下标

1. """
2. 如果假设输入一个数组 nums 和一个目标和 target，请你返回 nums 中能够凑出 target 的两个元素的数组下标
3. 输入：nums = [2,7,11,15], target = 9
4. 输出：[0,1]
5. """
6. hashmap = {}
7. for i, value in enumerate(nums):
8.     complement = target-value
9.     if complement in hashmap:
10.         return [i, hashmap[complement]]
11.     hashmap[value] = i
12.     return []

复制代码

(2) 字母异位数分组

1. """
2. 给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表
3. 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
4. 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
5. """
6. hashmap = collections.defaultdict(list)
7. for s in strs:
8.     key = "".join(sorted(list(s)))
9.     hashmap[key].append(s)
10. res = []
11. for key, value in hashmap.items():
12.     res.append(value)
13. return res

复制代码

(3) 最长连续序列

1. """
2. 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度
3. 输入：nums = [100,4,200,1,3,2]
4. 输出：4
5. """
6. res = 0
7. num_set = set(nums)
8. for num in num_set:
9.     if num-1 not in num_set:
10.         tmp = 1
11.         se = num+1
12.         while se in num_set:
13.             se += 1
14.             tmp += 1
15.         res = max(res, tmp)
16. return res

复制代码

双指针

(1) 移动零

1. """
2. 将所有 0 移动到数组的末尾，必须在不复制数组的情况下对原数组进行操作
3. 输入: nums = [0,1,0,3,12]
4. 输出: [1,3,12,0,0]
5. """
6. left = 0
7. for right in range(len(nums)):
8.     if nums[right]:
9.         nums[left], nums[right] = nums[right], nums[left]
10.         left += 1

复制代码

(2) 盛最多水的容器

1. """
2. 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水，返回容器可以储存的最大水量
3. 输入：[1,8,6,2,5,4,8,3,7]
4. 输出：49
5. """
6. res = 0
7. left, right = 0, len(height)-1
8. while left < right:
9.     area = (right-left) * min(height[right], height[left])
10.     if left >= right:
11.         right -= 1
12.     else:
13.         left += 1
14.     res = max(res, area)
15. return res

复制代码

(3) 三数之和

1. """
2. 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组
3. 输入：nums = [-1,0,1,2,-1,-4]
4. 输出：[[-1,-1,2],[-1,0,1]]
5. """
6. res = []
7. nums.sort()
8. for k in range(len(nums)-2):
9.     if nums[k] > 0: break
10.     if k > 0 and nums[k] == nums[k-1]: continue
11.     i, j = k+1, len(nums)-1
12.     while i < j:
13.         s = nums[k] + nums[i] + nums[j]
14.         if s < 0:
15.             i += 1
16.             while i < j and nums[i] == nums[i-1]: i += 1
17.         elif s > 0:
18.             j -= 1
19.             while i < j and nums[j] == nums[j+1]: j -= 1
20.         else:
21.             res.append([nums[k], nums[i], nums[j]])
22.             i += 1
23.             j -= 1
24.             while i < j and nums[i] == nums[i-1]: i += 1
25.             while i < j and nums[j] == nums[j+1]: j -= 1
26. return res

复制代码

(4) 接雨水
关键思绪：每个位置所装雨水 = min(它左边最高的，它右边最高的) - 该位置本身高度，双指针左右两边哪边高度低就能算一次哪边的雨水
[code]"""给定 n 个非负整数体现每个宽度为 1 的柱子的高度图，盘算按此分列的柱子，下雨之后能接多少雨水输入：height = [4,2,0,3,2,5]输出：9"""res = 0left, right = 0, len(height) - 1left_max, right_max = height[left], height[right]while left < right:    left_max = max(left_max,height[left])    right_max = max(right_max, height[right])    if left_max