哈希 & 双指针 & 滑动窗口（精选答案）

哈希

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

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

(2) 字母异位数分组

"""
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表
输入: 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[key].append(s)
res = []
for key, value in hashmap.items():
    res.append(value)
return res

(3) 最长连续序列

"""
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度
输入：nums = [100,4,200,1,3,2]
输出：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

双指针

(1) 移动零

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

(2) 盛最多水的容器

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

(3) 三数之和

"""
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 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[k] > 0: break 
    if k > 0 and nums[k] == nums[k-1]: continue 
    i, j = k+1, len(nums)-1
    while i < j: 
        s = nums[k] + nums[i] + nums[j]
        if s < 0:
            i += 1
            while i < j and nums[i] == nums[i-1]: i += 1
        elif s > 0:
            j -= 1
            while i < j and nums[j] == nums[j+1]: j -= 1
        else:
            res.append([nums[k], nums[i], nums[j]])
            i += 1
            j -= 1
            while i < j and nums[i] == nums[i-1]: i += 1
            while i < j and nums[j] == nums[j+1]: j -= 1
return res

(4) 接雨水

关键思路：每个位置所装雨水 = min(它左边最高的，它右边最高的) - 该位置本身高度，双指针左右两边哪边高度低就能算一次哪边的雨水

"""
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
输入：height = [4,2,0,3,2,5]
输出：9
"""
res = 0
left, right = 0, len(height) - 1
left_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 <= right_max:
        res += left_max - height[left]
        left += 1
    else:
        res += right_max - height[right]
        right -= 1
return res

滑动窗口

(1) 无重复字符的最长子串

"""
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度
"""
res = 0
window = set()
left, right = 0, 0
while right < len(s):
    if s[right] not in window:
        window.add(s[right])
        right += 1
        res = max(res, right-left)
    else:
        window.remove(s[left])
        left += 1   
return res

(2) 找出字符串中所有字母异位置词

"""
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
"""
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[s[i]] += 1
    st = i-p_len+1
    if window == p_counter:
        res.append(st)
    window[s[st]] -= 1
    if window[s[st]] == 0:
        del window[s[st]]
return res