哈希 & 双指针 & 滑动窗口
哈希(1) twosum 问题返回数组下标
"""如果假设输入一个数组 nums 和一个目标和 target，请你返回 nums 中能够凑出 target 的两个元素的数组下标输入：nums = , target = 9输出："""hashmap = {}for i, value in enumerate(nums): complement = target-value if complement in hashmap: return ] hashmap = 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.append(s)res = []for key, value in hashmap.items(): res.append(value)return res(3) 最长连续序列
"""给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度输入：nums = 输出：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) 移动零
"""将所有 0 移动到数组的末尾，必须在不复制数组的情况下对原数组进行操作输入: nums = 输出: """left = 0for right in range(len(nums)): if nums: nums, nums = nums, nums left += 1(2) 盛最多水的容器
"""给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水，返回容器可以储存的最大水量输入：输出：49 """res = 0left, right = 0, len(height)-1while left < right: area = (right-left) * min(height, height) if left >= right: right -= 1 else: left += 1 res = max(res, area)return res(3) 三数之和
"""给你一个整数数组 nums ，判断是否存在三元组 , nums, nums] 满足 i != j、i != k 且 j != k ，同时还满足 nums + nums + nums == 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 > 0: break if k > 0 and nums == nums: continue i, j = k+1, len(nums)-1 while i < j: s = nums + nums + nums if s < 0: i += 1 while i < j and nums == nums: i += 1 elif s > 0: j -= 1 while i < j and nums == nums: j -= 1 else: res.append(, nums, nums]) i += 1 j -= 1 while i < j and nums == nums: i += 1 while i < j and nums == nums: j -= 1return res(4) 接雨水
关键思路：每个位置所装雨水 = min(它左边最高的，它右边最高的) - 该位置本身高度，双指针左右两边哪边高度低就能算一次哪边的雨水
"""给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水输入：height = 输出：9"""res = 0left, right = 0, len(height) - 1left_max, right_max = height, heightwhile left < right: left_max = max(left_max,height) right_max = max(right_max, height) if left_max
页:
[1]