【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 0
        max_len,cur = 1,1
        nums.sort()
        for i in range(0,len(nums)-1):
            if nums[i+1] - nums[i] == 1:
                cur += 1
                max_len = cur if cur > max_len else max_len
            elif nums[i+1] == nums[i]:
                continue
            else:
                cur = 1
        return 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,0
        while fast < len(nums):
            while nums[slow] !=0 and slow < len(nums)-1:
                slow += 1
                fast += 1
            while nums[fast] == 0 and  fast < len(nums)-1:
                fast += 1
            nums[slow],nums[fast] = nums[fast],nums[slow]
            slow += 1
            fast += 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 = 0
        left,right = 0,len(height)-1
        while left < right:
            cur = (right-left) * min(height[left],height[right])
            ans = cur if cur > ans else ans
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return 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 ans
        
        nums.sort()
        for i in range(length):
            if nums[i] > 0:
                return ans
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left = i + 1
            right = length - 1
            while 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 += 1
                    while left<right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif nums[i] + nums[left] + nums[right] < 0:
                    left += 1
                else:
                    right -= 1
        return 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 = 0
        left,right = 0,len(height)-1
        max_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 += 1
            else:
                ans += max_right - height[right]
                right -= 1
        return 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 = 0
        cur = ""
        i = 0
        
        while i < len(s):
            if s[i] not in cur:
                cur += s[i]
                max_l = max(max_l,len(cur))
                i += 1
            else:
                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 res
        p_cnt = [0] * 26
        s_cnt = [0] * 26
        for i in range(m):
            p_cnt[ord(p[i]) - ord('a')] += 1
            s_cnt[ord(s[i]) - ord('a')] += 1
        if s_cnt == p_cnt:
            res.append(0)
        
        for i in range(m, n):
            s_cnt[ord(s[i - m]) - ord('a')] -= 1
            s_cnt[ord(s[i]) - ord('a')] += 1
            if 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 = 0
        presum = collections.defaultdict(int)
        presum[0] = 1
        cur_presum = 0

        for n in nums:
            cur_presum += n
            ans += presum[cur_presum-k]
            presum[cur_presum] += 1
        return 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] += 1
        ans = (0,float('inf'))

        # 增加右边界使滑窗包含t
        i = 0
        for j,c in enumerate(s):
            if need[c] > 0:
                needCnt -= 1
            need[c] -= 1
            # 收缩左边界直到无法再去掉元素
            if needCnt == 0:
                while True:
                    ch = s[i]
                    if need[ch] == 0:
                        break
                    else:
                        need[ch] += 1
                        i += 1
                if j-i < ans[1]-ans[0]:
                    ans = (i,j+1)
                # i多增加一个位置，准备开始下一次循环
                need[s[i]] += 1
                needCnt += 1
                i += 1
        return ""if ans[1]>s_len else s[ans[0]:ans[1]]