哈希 & 双指针 & 滑动窗口

哈希

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

1. """如果假设输入一个数组 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) 字母异位数分组

1. """给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表输入: 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) 最长连续序列

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

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

复制代码

(2) 盛最多水的容器

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

1. """给你一个整数数组 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 -= 1return res

复制代码

(4) 接雨水
关键思路：每个位置所装雨水 = min(它左边最高的，它右边最高的) - 该位置本身高度，双指针左右两边哪边高度低就能算一次哪边的雨水
[code]"""给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水输入：height = [4,2,0,3,2,5]输出：9"""res = 0left, right = 0, len(height) - 1left_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