目录
前言
一、哈希
1.两数之和
2. 字母异位词分组
3. 最长连续序列
二、双指针
1. 移动零
2. 盛最多水的容器
3. 三数之和
4. 接雨水
三、滑动窗口
1. 无重复字符的最长子串
2. 找到字符串中所有字母异位词
前言
一、哈希：两数之和，字母异位词分组，最长连续序列。
二、双指针：移动零，盛最多水的容器，三数之和，接雨水。
三、滑动窗口：无重复字符的最长子串，找到字符串中所有字母异位词。
一、哈希
1.两数之和
原题链接：1. 两数之和 - 力扣（LeetCode）
class Solution(object):def twoSum(self, nums, target):n = len(nums)for i in range(n):for j in range(i+1, n):if nums[i] + nums[j] == target:return [i, j]2. 字母异位词分组
原题链接：49. 字母异位词分组 - 力扣（LeetCode）
class Solution(object):def groupAnagrams(self, strs):res = []dicts = {}for s in strs:s_ = ''.join(sorted(s))if s_ in dicts:dicts[s_].append(s)else:dicts[s_] = [s]return list(dicts.values())
3. 最长连续序列
原题链接：128. 最长连续序列 - 力扣（LeetCode）
class Solution(object):def longestConsecutive(self, nums):# left, right双指针res = 0nums = set(nums)for left in nums:if left-1 not in nums: # 找片段左端点leftright = left + 1while right in nums: # 找片段右端点rightright += 1res = max(res, right-left)return res二、双指针
1. 移动零
原题链接：283. 移动零 - 力扣（LeetCode）
class Solution(object):def moveZeroes(self, nums):for i, n in enumerate(nums):if n == 0:nums.remove(n)nums.append(n)return nums2. 盛最多水的容器
原题链接：11. 盛最多水的容器 - 力扣（LeetCode）
# 考点：左右指针（left & right）
class Solution(object):def maxArea(self, height):n = len(height)left, right = 0, n-1res = 0while left < right:area = min(height[left], height[right]) * (right - left)res = max(res, area)if height[left] <= height[right]:left +=1else:right -=1return res3. 三数之和
原题链接：15. 三数之和 - 力扣（LeetCode）
# 考点：左右指针（left & right）
class Solution(object):def threeSum(self, nums):nums.sort()if min(nums) > 0:return []n = len(nums)res = []for i in range(n):if i>0 and nums[i] == nums[i-1]:continueleft, right = i+1, n-1while left < right:if nums[i]+nums[left]+nums[right] == 0:while left < right and nums[left] == nums[left+1]:left += 1while left < right and nums[right] == nums[right-1]:right -= 1res.append([nums[i], nums[left], nums[right]])left += 1right -= 1elif nums[i]+nums[left]+nums[right] < 0:left += 1else:right -= 1return res4. 接雨水
原题链接：42. 接雨水 - 力扣（LeetCode）
class Solution(object):def trap(self, height):# prefix_max最大前缀, suffix_max最大后缀, min(prefix_max, suffix_max) - hres = 0n = len(height)prefix_max = [0] * nprefix_max[0] = height[0]for i in range(1, n):prefix_max[i] = max(prefix_max[i-1], height[i])suffix_max = [0] * nsuffix_max[-1] = height[-1]for i in range(n-2, -1, -1):suffix_max[i] = max(height[i], suffix_max[i+1])for h, prefix, suffix in zip(height, prefix_max, suffix_max):res = res + min(prefix, suffix) - hreturn res三、滑动窗口
1. 无重复字符的最长子串
原题链接：3. 无重复字符的最长子串 - 力扣（LeetCode）
# 考点：滑窗（不定窗口），快慢指针
class Solution(object):def lengthOfLongestSubstring(self, s):from collections import Countercnt = Counter()left = 0 res = 0for right, c in enumerate(s):cnt[c] += 1while cnt[c] > 1:cnt[s[left]] -= 1left += 1res = max(res, right-left+1)return res2. 找到字符串中所有字母异位词
原题链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
class Solution(object):def findAnagrams(self, s, p):# 考点：滑窗（固定窗口），快慢指针from collections import Counterleft = 0res = []cnt_p = Counter(p)cnt_s = Counter()for right, c in enumerate(s):cnt_s[c] += 1while right - left + 1 == len(p):if cnt_s == cnt_p:res.append(left)if s[left] in cnt_s:cnt_s[s[left]] -= 1if cnt_s[s[left]] == 0:del cnt_s[s[left]]left += 1return res
