哈希 & 双指针 & 滑动窗口（精选答案）
<h2 id="哈希">哈希</h2><p><strong>(1) twosum 问题返回数组下标</strong></p>
<pre><code class="language-python">"""
如果假设输入一个数组 nums 和一个目标和 target，请你返回 nums 中能够凑出 target 的两个元素的数组下标
输入：nums = , target = 9
输出：
"""
hashmap = {}
for i, value in enumerate(nums):
complement = target-value
if complement in hashmap:
return ]
hashmap = i
return []
</code></pre>
<p><strong>(2) 字母异位数分组</strong></p>
<pre><code class="language-python">"""
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
"""
hashmap = collections.defaultdict(list)
for s in strs:
key = "".join(sorted(list(s)))
hashmap.append(s)
res = []
for key, value in hashmap.items():
res.append(value)
return res
</code></pre>
<p><strong>(3) 最长连续序列</strong></p>
<pre><code class="language-python">"""
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度
输入：nums =
输出：4
"""
res = 0
num_set = set(nums)
for num in num_set:
if num-1 not in num_set:
tmp = 1
se = num+1
while se in num_set:
se += 1
tmp += 1
res = max(res, tmp)
return res
</code></pre>
<h2 id="双指针">双指针</h2>
<p><strong>(1) 移动零</strong></p>
<pre><code class="language-python">"""
将所有 0 移动到数组的末尾，必须在不复制数组的情况下对原数组进行操作
输入: nums =
输出:
"""
left = 0
for right in range(len(nums)):
if nums:
nums, nums = nums, nums
left += 1
</code></pre>
<p><strong>(2) 盛最多水的容器</strong></p>
<pre><code class="language-python">"""
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水，返回容器可以储存的最大水量
输入：
输出：49
"""
res = 0
left, right = 0, len(height)-1
while left < right:
area = (right-left) * min(height, height)
if left >= right:
right -= 1
else:
left += 1
res = max(res, area)
return res
</code></pre>
<p><strong>(3) 三数之和</strong></p>
<pre><code class="language-python">"""
给你一个整数数组 nums ，判断是否存在三元组 , nums, nums] 满足 i != j、i != k 且 j != k ，同时还满足 nums + nums + nums == 0 。请你返回所有和为 0 且不重复的三元组
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
"""
res = []
nums.sort()
for k in range(len(nums)-2):
if nums > 0: break
if k > 0 and nums == nums: continue
i, j = k+1, len(nums)-1
while i < j:
s = nums + nums + nums
if s < 0:
i += 1
while i < j and nums == nums: i += 1
elif s > 0:
j -= 1
while i < j and nums == nums: j -= 1
else:
res.append(, nums, nums])
i += 1
j -= 1
while i < j and nums == nums: i += 1
while i < j and nums == nums: j -= 1
return res
</code></pre>
<p><strong>(4) 接雨水</strong></p>
<p>关键思路：每个位置所装雨水 = min(它左边最高的，它右边最高的) - 该位置本身高度，双指针左右两边哪边高度低就能算一次哪边的雨水</p>
<pre><code class="language-python">"""
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
输入：height =
输出：9
"""
res = 0
left, right = 0, len(height) - 1
left_max, right_max = height, height
while left < right:
left_max = max(left_max,height)
right_max = max(right_max, height)
if left_max <= right_max:
res += left_max - height
left += 1
else:
res += right_max - height
right -= 1
return res
</code></pre>
<h2 id="滑动窗口">滑动窗口</h2>
<p><strong>(1) 无重复字符的最长子串</strong></p>
<pre><code class="language-python">"""
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度
"""
res = 0
window = set()
left, right = 0, 0
while right < len(s):
if s not in window:
window.add(s)
right += 1
res = max(res, right-left)
else:
window.remove(s)
left += 1
return res
</code></pre>
<p><strong>(2) 找出字符串中所有字母异位置词</strong></p>
<pre><code class="language-python">"""
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引
输入: s = "cbaebabacd", p = "abc"
输出:
"""
res = []
s_len, p_len = len(s), len(p)
p_counter = collections.Counter(p)
window = collections.Counter(s[:p_len-1])
for i in range(p_len-1, s_len):
window] += 1
st = i-p_len+1
if window == p_counter:
res.append(st)
window] -= 1
if window] == 0:
del window]
return res
</code></pre><br><br>
来源：https://www.cnblogs.com/mianmaner/p/19715055
頁:
[1]