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 num1 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 k1, 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[j1]: 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[j1]: 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
