哈希

(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