hot100
1. 两数之和
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
d = {}
for i, num in enumerate(nums):
if target - num in d:
return [i, d[target- num]]
d[num] = i
49. 字母异位词分组
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = {}
for str in strs:
str_ = "".join(sorted(str))
if str_ not in d:
d[str_] = [str]
else:
d[str_].append(str)
return list(d.values())
128. 最长连续序列✨
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
s = set(nums)
max_len = 0
for i in s:
if i - 1 not in s: # 只需要从开头开始枚举
j = i
len_ = 0
while (j in s):
j += 1
len_ += 1
max_len = max(max_len, len_)
return max_len
283. 移动零
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
ln = len(nums)
for i in range(ln):
if nums[i] == 0:
j = i
while j + 1 < ln and nums[j] == 0:
j += 1
print(i, j)
nums[i], nums[j] = nums[j], nums[i]
## 官方
def moveZeroes(self, nums: List[int]) -> None:
n = len(nums)
left = right = 0
while right < n:
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
11. 成水最多的容器
class Solution:
def maxArea(self, h: List[int]) -> int:
l, r = 0, len(h) - 1
res = 0
while l < r:
area = min(h[l], h[r]) * (r - l)
res = max(res, area)
if h[l] <= h[r]:
l += 1
else:
r -= 1
return res
15.三数之和
推荐题解：https://leetcode.cn/problems/3sum/solutions/11525/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
ln = len(nums)
if ln < 3:
return res
for a in range(ln - 2):
if nums[a] > 0:
return res
if a > 0 and nums[a] == nums[a - 1]:
continue
b, c = a + 1, ln - 1
while b < c:
s = nums[a] + nums[b] + nums[c]
if s < 0:
b += 1
while b < c and nums[b] == nums[b - 1]: b += 1
elif s > 0:
c -= 1
while b < c and nums[c] == nums[c + 1]: c -= 1
else:
res.append([nums[a], nums[b], nums[c]])
b += 1
c -= 1
while b < c and nums[b] == nums[b - 1]: b += 1
while b < c and nums[c] == nums[c + 1]: c -= 1
return res
42. 接雨水
class Solution:
def trap(self, h: List[int]) -> int:
res = 0
stack = []
for i in range(len(h)):
while stack and h[stack[-1]] < h[i]:
cur = stack.pop()
if not stack: #前面也没有高的柱子，不可能接到雨水
break
height = min(h[i], h[stack[-1]]) - h[cur] #当前能接到的雨水高度
res += (i - stack[-1] - 1) * height
stack.append(i)
return res
3. 无重复字符的最长子串
def lengthOfLongestSubstring(self, s: str) -> int:
s_ = set()
res = 0
l, r = 0, 0
while r < len(s):
while r < len(s) and s[r] not in s_:
s_.add(s[r])
r += 1
res = max(res, r - l)
while l < r and r < len(s) and s[l] != s[r]:
s_.remove(s[l])
l += 1
l += 1
r += 1
return res
比较简略的c++写法：
int lengthOfLongestSubstring(string s) {
int len = 0;
int n = s.size();
unordered_set<char> set;
for (int i = 0, j = 0; j < n; j++) {
while (set.count(s[j]))
set.erase(s[i++]);
set.insert(s[j]);
len = max(len, j - i + 1);
}
return len;
}
438. 找到字符串中所有字母异位词
固定滑动窗口
def findAnagrams(self, s: str, p: str) -> List[int]:
slen , plen = len(s), len(p)
if slen < plen:
return []
ans = []
s_ = [0] * 26
p_ = [0] * 26
for i in range(plen):
s_[ord(s[i]) - 97] += 1
p_[ord(p[i]) - 97] += 1
if s_ == p_:
ans.append(0)
for i in range(slen - plen):
s_[ord(s[i]) - 97] -= 1
s_[ord(s[i + plen]) - 97] += 1
if s_ == p_:
ans.append(i + 1)
return ans
560. 和为 K 的子数组
前缀和 + hash（cnt保存当前以0为左边界所有前缀和出现的次数）
def subarraySum(self, nums: List[int], k: int) -> int:
ans = s = 0
cnt = defaultdict(int)
for x in nums:
cnt[s] += 1
s += x
ans += cnt[s - k] ##之间为k
return ans
239. 滑动窗口最大值
简单做法：堆保存数据，右移时判断堆顶元素是否在窗口内
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
q = [(-nums[i], i) for i in range(k)]
heapq.heapify(q)
ans = [-q[0][0]]
for i in range(k, n):
heapq.heappush(q, (-nums[i], i))
while (q[0][1] < i - k + 1):
heapq.heappop(q)
ans.append(-q[0][0])
return ans
优化：单调队列（不需要维护所有元素，只需要维护一个单调递减的队列元素，左侧的小元素相比于右侧大元素永远不可能成为答案）
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans = [0] * (len(nums) - k + 1)
q = deque()
for i, x in enumerate(nums):
while q and nums[q[-1]] <= x:
q.pop()
q.append(i)
left = i - k + 1
if q[0] < left:
q.popleft()
if left >= 0:
ans[left] = nums[q[0]]
return ans