第一题 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
题解：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
nums.sort()
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
j = i + 1
k = n - 1
if nums[i] + nums[j] + nums[j + 1] > 0:
break
if nums[i] + nums[k - 1] + nums[k] < 0:
continue
while j < k:
if nums[i] + nums[j] + nums[k] > 0:
k -= 1
elif nums[i] + nums[j] + nums[k] < 0:
j += 1
else:
res.append([nums[i], nums[j], nums[k]])
j += 1
k -= 1
while j < k and nums[j] == nums[j - 1]:
j += 1
while j < k and nums[k] == nums[k + 1]:
k -= 1
return res
第二题 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
题解：
class Solution:
def trap(self, height: List[int]) -> int:
mh = max(height)
l = r = left = right = t = 0
for i in height:
l = max(l, i)
left += (mh - l) if (mh - l) > 0 else 0
t += i
for i in height[::-1]:
r = max(r, i)
right += (mh - r) if (mh - r) > 0 else 0
return len(height) * mh - right - left - t
第三题 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
题解:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l = r = res = 0
arr = []
while r < len(s):
if s[r] not in arr:
arr.append(s[r])
r += 1
else:
while s[r] in arr:
arr.pop(0)
l += 1
res = max(res, r - l)
return res
第四题 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
res = []
cnt = Counter(p)
j = 0
for i in range(len(s)):
cnt[s[i]] -= 1
while cnt[s[i]] < 0:
cnt[s[j]] += 1
j += 1
if i - j + 1 == len(p):
res.append(j)
return res
第五题 和为K的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
题解：
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
cnt = defaultdict(int)
res = s = 0
for n in nums:
res += cnt[s - k]
cnt[s] += 1
s += n
res += cnt[s - k]
return res