【leetcode刷题之路】面试经典hot100（1）——哈希+双指针+滑动窗口+子串

1 哈希

1.1 【哈希】【模拟】两数之和

题目链接：https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked

用哈希表解题，当遍历数组元素的过程中，只需要找到target与当前元素的差值是不是在数组中即可，比如：

（1）样例1

设哈希表为ht={ }，nums=[2,7,11,15]，target=9，开始遍历元素：

• 第一个元素为2，差值为7，7不在哈希表中，把2和下标加入哈希表，此时ht={2 : 0}；
• 第二个元素为7，差值为2，2在哈希表中，结果为[0,1]。

（2）样例2

设哈希表为ht={ }，nums=[3,2,4]，target=6，开始遍历元素：

• 第一个元素为3，差值为3，3不在哈希表中，把3和下标加入哈希表，此时ht={3 : 0}；
• 第二个元素为2，差值为4，4不在哈希表中，把4和下标加入哈希表，此时ht={3 : 0, 4 : 1}；
• 第三个元素为4，差值为2，2在哈希表中，结果为[1,2]。

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:ht = {}for i,n in enumerate(nums):if target-n in ht:return [ht[target-n],i]ht[n] = i

1.2 【哈希】【字符串】字母异位词

题目链接：https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked

对每个单词的所有字母进行排序，对于字母异位词的单词，它们排序之后的结果应该是一样的，因为他们的各个字母的次数是一样的，所以基于这个来划分字母异位词。

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

1.3 【模拟】【哈希】最长连续序列

题目链接：https://leetcode.cn/problems/longest-consecutive-sequence/submissions/552801160/?envType=study-plan-v2&envId=top-100-liked

直接对原数组进行排序，但是要考虑到两种情况：（1）数组为空；（2）数组中有重复元素。

class Solution:def longestConsecutive(self, nums: List[int]) -> int:if len(nums) == 0:return 0max_len,cur = 1,1nums.sort()for i in range(0,len(nums)-1):if nums[i+1] - nums[i] == 1:cur += 1max_len = cur if cur > max_len else max_lenelif nums[i+1] == nums[i]:continueelse:cur = 1return max_len

2 双指针

2.1 【双指针】【数组】移动零

题目链接：https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked

设置快慢指针，快指针找到第一个非零元素，慢指针找到第一个零元素，交换位置即可。

class Solution:def moveZeroes(self, nums: List[int]) -> None:slow,fast = 0,0while fast < len(nums):while nums[slow] !=0 and slow < len(nums)-1:slow += 1fast += 1while nums[fast] == 0 and  fast < len(nums)-1:fast += 1nums[slow],nums[fast] = nums[fast],nums[slow]slow += 1fast += 1

2.2 【双指针】【数组】盛最多水的容器

题目链接：https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked

设置左右指针，每次遍历时容器的体积取决于两边最低的高度是多少，所以每次遍历的时候哪边的高度更小，哪边就向里移动一格。

class Solution:def maxArea(self, height: List[int]) -> int:ans = 0left,right = 0,len(height)-1while left < right:cur = (right-left) * min(height[left],height[right])ans = cur if cur > ans else ansif height[left] < height[right]:left += 1else:right -= 1return ans

2.3 【双指针】【数组】三数之和

题目链接：https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked

先排序，然后去重，每次固定一个数，在剩下的范围中用双指针找合为0的三元组。

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:length = len(nums)ans = []if length < 3:return ansnums.sort()for i in range(length):if nums[i] > 0:return ansif i > 0 and nums[i] == nums[i-1]:continueleft = i + 1right = length - 1while left < right:if nums[i] + nums[left] + nums[right] == 0:ans.append([nums[i],nums[left],nums[right]])while left<right and nums[left] == nums[left+1]:left += 1while left<right and nums[right] == nums[right-1]:right -= 1left += 1right -= 1elif nums[i] + nums[left] + nums[right] < 0:left += 1else:right -= 1return ans

2.4 【双指针】接雨水

题目链接：https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked

双指针解决，分别记录左边和右边的最大值，然后依次从两边往中间记录差值，最后差值的和即为接雨水量。

class Solution:def trap(self, height: List[int]) -> int:ans = 0left,right = 0,len(height)-1max_left,max_right = height[left],height[right]while left < right:max_left = max(max_left,height[left])max_right = max(max_right,height[right])if max_left < max_right:ans += max_left - height[left]left += 1else:ans += max_right - height[right]right -= 1return ans 

3 滑动窗口

3.1 【滑动窗口】【字符串】无重复字符的最长子串

题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked

设置一个滑动窗口，如果遍历到的字母没有在窗口内出现过，则窗口长度+1，否则把窗口左边的元素剔除，直到窗口内没有重复元素，每次窗口滑动时记录是否为最大值。

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:max_l = 0cur = ""i = 0while i < len(s):if s[i] not in cur:cur += s[i]max_l = max(max_l,len(cur))i += 1else:cur = cur[1:]return max_l

3.2 【滑动窗口】【哈希】找到字符串中所有字母异位词

题目链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked

统计字符串p中字母的出现次数，当滑动窗口移动时，判断窗口内字母的次数和p是否一致，一致的话记录此时的下标。

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:n, m, res = len(s), len(p), []if n < m: return resp_cnt = [0] * 26s_cnt = [0] * 26for i in range(m):p_cnt[ord(p[i]) - ord('a')] += 1s_cnt[ord(s[i]) - ord('a')] += 1if s_cnt == p_cnt:res.append(0)for i in range(m, n):s_cnt[ord(s[i - m]) - ord('a')] -= 1s_cnt[ord(s[i]) - ord('a')] += 1if s_cnt == p_cnt:res.append(i - m + 1)return res

4 子串

4.1 【前缀和】和为 K 的子数组

题目链接：https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked

利用前缀和的思想，假设目前的前缀和为presum，我只需要找到在这之前前缀和为presum-k的情况一共出现了多少次，作差子数组和就是k。

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:ans = 0presum = collections.defaultdict(int)presum[0] = 1cur_presum = 0for n in nums:cur_presum += nans += presum[cur_presum-k]presum[cur_presum] += 1return ans

4.2 【滑动窗口】滑动窗口最大值

题目链接：https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked

维护一个单调递减的双端队列，保证队列首元素一直是目前的最大值。

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:ans = []q = deque()for i,x in enumerate(nums):while q and nums[q[-1]] < x:q.pop()q.append(i)if i-q[0] >= k:q.popleft()if i >= k-1:ans.append(nums[q[0]])return ans

4.3 【字符串】【滑动窗口】最小覆盖子串

题目链接：https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked

1.不断增加使滑动窗口增大，直到窗口包含了t的所有元素；

2.不断增加使滑动窗口缩小，将不必要的元素排除在外,直到碰到一个必须包含的元记录此时滑动窗口的长度，并保存最小值；

3.再增加一个位置，这个时候滑动窗口肯定不满足条件了，继续从步骤一开始执行，寻找新的满足条件的滑动窗口。

class Solution:def minWindow(self, s: str, t: str) -> str:s_len, t_len, needCnt = len(s), len(t), len(t)need = collections.defaultdict(int)for c in t:need[c] += 1ans = (0,float('inf'))# 增加右边界使滑窗包含ti = 0for j,c in enumerate(s):if need[c] > 0:needCnt -= 1need[c] -= 1# 收缩左边界直到无法再去掉元素if needCnt == 0:while True:ch = s[i]if need[ch] == 0:breakelse:need[ch] += 1i += 1if j-i < ans[1]-ans[0]:ans = (i,j+1)# i多增加一个位置，准备开始下一次循环need[s[i]] += 1needCnt += 1i += 1return ""if ans[1]>s_len else s[ans[0]:ans[1]]