Leetcode hot100

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1:

输入nums = [2,7,11,15], target = 9

输出[0,1]

解释:因为 nums[0] + nums[1] == 9,返回 [0, 1]

Answer:

1
2
3
4
5
6
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i]+nums[j] == target:
return [i, j]

49. 字母异位词分组

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出[["bat"],["nat","tan"],["ate","eat","tea"]]

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def match(self, str):
return "".join(sorted(str))

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagram_dict = {}
for word in strs:
sorted_word = self.match(word)
if sorted_word in anagram_dict:
anagram_dict[sorted_word].append(word)
else:
anagram_dict[sorted_word] = [word]
return list(anagram_dict.values())

128. 最长连续序列

给定一个未排序的整数数组 nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 \(O(n)\) 的算法解决此问题。

示例 1:

输入nums = [100,4,200,1,3,2]

输出4

解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4

Answer:

排序的时间复杂度为O(nlogn)!!!因此不能排序

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
ans = 0
set_nums = set(nums) # 转为集合去重
for x in set_nums:
if x - 1 in set_nums:
continue
y = x + 1
while y in set_nums:
y += 1
ans = max(ans, y - x)
return ans

283. Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non - zero elements.

Note that you must do this in - place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]

Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]

Output: [0]

Answer 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
count = 0
for i in nums:
if i == 0:
count += 1
for i in range(len(nums)):
if nums[i] != 0:
continue
for j in range(i+1, len(nums)):
if nums[j] != 0:
nums[i] = nums[j]
i += 1
for z in range(len(nums)-count, len(nums)):
nums[z] = 0
return nums

Answer 2:

1
2
3
4
5
6
7
8
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
i0 = 0
for i in range(len(nums)):
if nums[i]:
nums[i], nums[i0] = nums[i0], nums[i]
i0 += 1
# by:灵茶山艾府

11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x - axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: The above vertical lines are represented by the array [1,8,6,2,5,4,8,3,7]. In this case, the maximum area of water (the blue - shaded section) that the container can hold is 49.

Example 2

Input: height = [1,1]

Output: 1

Answer 1:

Brute-force search,NONONO

1
2
3
4
5
6
7
class Solution:
def maxArea(self, height: List[int]) -> int:
maxarea = 0
for i in range(len(height)):
for j in range(i+1, len(height)):
maxarea = max(maxarea, (j-i)* min(height[j],height[i]))
return maxarea

Answer 2:

Great !!!

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def maxArea(self, height: List[int]) -> int:
i , j, maxarea = 0, len(height)-1, 0
while i < j:
if height[i] < height[j]:
maxarea = max(maxarea, (j-i) * height[i])
i += 1
else:
maxarea = max(maxarea, (j-i) * height[j])
j -= 1
return maxarea

15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Explanation: 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.
The distinct triplets are [-1,0,1] and [-1,-1,2].

Notice that the order of the output and the order of the triplets does not matter.

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
nums = sorted(nums)
i = 0
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]: # i 是可以跳过重复数字的
continue
if nums[i] > 0: # 优化1
break
if nums[i] + nums[i+1] + nums[i+2] > 0: # 优化2
break
if nums[i] + nums[-1] + nums[-2] < 0: # 优化3
continue
k = i + 1
j = len(nums)-1
while k < j: # 剩下的问题是两数和
if nums[i] + nums[k] + nums[j] < 0:
k += 1
elif nums[i] + nums[k] + nums[j] > 0:
j -= 1
else:
result.append([nums[i], nums[k], nums[j]])
j -= 1
while k < j and nums[j] == nums[j+1]: # j k 排除重复数字时,都是和考虑过的数字比较!!!
j -= 1
k += 1
while k < j and nums[k] == nums[k-1]:
k += 1
return result

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without duplicate characters.

Example 1:

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3.

Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Answer:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
result = left = 0
count = defaultdict(int) # 使用 defaultdict(int) 不需要预先检查键是否存在
for right, c in enumerate(s):
count[c]+=1
while count[c]>1:
count[s[left]]-=1
left+=1
result = max(result, right - left +1)
return result

438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

Example 1:

Input: s = "cbaebabacd", p = "abc"

Output: [0,6]

Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"

Output: [0,1,2]

Explanation:

The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

考察点是滑动窗口,与前一题有点像

Answer 1:

能够通过大部分样例的解法,比较笨

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
result = []
length = len(p)
p = "".join(sorted(p))
for i in range(len(s)-length+1):
string = ""
for j in range(length):
string += s[i+j]
string = "".join(sorted(string))
if string == p:
result.append(i)
return result

Answer 2:

采用了定长滑动窗口的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
result = []
length = len(p)
cnt_p = Counter(p) # Counter 用于统计可哈希对象的出现次数
cnt_s = Counter()
for right, c in enumerate(s):
cnt_s[c]+=1
left = right - length + 1
if left < 0:
continue
if cnt_s == cnt_p:
result.append(left)
cnt_s[s[left]] -= 1 # 因为定长滑动窗口,所以需要把左边的元素减掉
return result

Answer 3:

采用不定长滑动窗口,思路参考:by 灵茶山艾府

枚举子串 s' 的右端点,如果发现 s' 其中一种字母的出现次数大于 p 的这种字母的出现次数,则右移 s' 的左端点。如果发现 s' 的长度等于 p 的长度,则说明 s' 的每种字母的出现次数,和 p 的每种字母的出现次数都相同,那么 s'p 的异位词。

证明:内层循环结束后,s' 的每种字母的出现次数,都小于等于 p 的每种字母的出现次数。如果 s' 的其中一种字母的出现次数比 p 的小,那么 s' 的长度必然小于 p 的长度。所以只要 s' 的长度等于 p 的长度,就说明 s' 的每种字母的出现次数,和 p 的每种字母的出现次数都相同,s'p 的异位词,把 s' 左端点下标加入答案。

代码实现时,可以把 cntScntP 合并成一个 cnt: - 对于 p 的字母 c,把 cnt[p] 加一。 - 对于 s' 的字母 c,把 cnt[c] 减一。 - 如果 cnt[c] < 0,说明窗口中的字母 c 的个数比 p 的多,右移左端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
result = []
length = len(p)
cnt_p = Counter(p)
cnt_s = Counter()
left = 0
for right, c in enumerate(s):
cnt_s[c]+=1
while cnt_s[c] > cnt_p[c]:
cnt_s[s[left]] -= 1
left += 1
if right - left + 1 == length:
result.append(left)
return result

560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.
子数组是数组中元素的连续非空序列。
注意是连续的!!!

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

1
2
3
问:为什么这题不适合用滑动窗口做?
答:滑动窗口需要满足单调性,当右端点元素进入窗口时,窗口元素和是不能减少的。本题 nums 包含负数,当负数进入窗口时,窗口左端点反而要向左移动,导致算法复杂度不是线性的。
---by:灵茶山艾府

在解决本题之前,需要练习前缀和模板题303!!!

Answer 1:

前缀和问题,使用前缀和字典记录前缀和的出现次数,然后遍历数组,计算当前前缀和减去目标值k的差值在字典中出现的次数,累加到结果中。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
prefix_sum = {0: 1} # 前缀和字典,初始值为前缀和为0出现1次
current_sum = 0
count = 0
for num in nums:
current_sum += num
if current_sum - k in prefix_sum:
count += prefix_sum[current_sum - k]
prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
return count

Answer 2:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
fsum = [0] * (len(nums) + 1)
ans = 0
for index, n in enumerate(nums):
fsum[index+1] = fsum[index] + n
cnt = defaultdict(int)
for s in fsum:
ans += cnt[s-k]
cnt[s] += 1
return ans

Answer 3:

还可以优化成一次遍历即可实现:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
fsum = [0] * (len(nums) + 1)
ans = 0
cnt = defaultdict(int)
cnt[0] = 1
s = 0
for n in nums:
s += n
ans += cnt[s-k]
cnt[s] += 1
return ans

303. Range Sum Query - Immutable

Given an integer array nums, handle multiple queries of the following type:

  1. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

  • NumArray(int[] nums) Initializes the object with the integer array nums.
  • int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"] [[-2, 0, 3, -5, 2, -1], [0, 2], [2, 5], [0, 5]]

Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

303连题目都看不懂。。。绝了。。。

Answer 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
class NumArray:

def __init__(self, nums: List[int]):
self.fsum = [0] * (len(nums) + 1)
for i, n in enumerate(nums):
self.fsum[i+1] = self.fsum[i] + n

def sumRange(self, left: int, right: int) -> int:
return self.fsum[right+1] - self.fsum[left]

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

303做完再回去看560应该就能看懂了

53. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Answer 1:

遍历解法,能通过绝大多数测试,复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = -10000
fsum = [0]* (len(nums)+1)
for index, n in enumerate(nums):
fsum[index+1] = fsum[index] + n
for i in range(len(nums)+1):
for j in range(i+1,len(nums)+1):
ans = max(ans, fsum[j]-fsum[i])
return ans

Answer 2:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = nums[0]
current_array = 0
for n in nums:
if current_array < 0:
current_array = n
else:
current_array += n
ans = max(current_array, ans)
return ans

这种解法的主角是当前遍历的对象n,如果当前数组的和小于0,那么当前数组的和就等于n,否则就加上n,然后比较当前数组的和和ans的大小,如果当前数组的和大于ans,那么ans就等于当前数组的和

56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping

Answer 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def detect(self, list1, list2):
if list1[1] < list2[0]:
return False
elif list1[0] > list2[1]:
return False
else:
return True
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
intervals.sort(key=lambda x: x[0]) # 按照左端点排序
ans = [intervals[0]]
for interval in intervals:
last_interval = ans[-1]
if self.detect(last_interval, interval):
ans[-1] = [min(last_interval[0],interval[0]), max(last_interval[1], interval[1])]
else:
ans.append(interval)
return ans

189. Rotate Array

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Answer 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
# 处理 k 大于数组长度的情况
k = k % n
# 创建临时数组存储后 k 个元素
temp = nums[-k:]
# 将数组前 n - k 个元素向后移动 k 个位置
for i in range(n - 1, k - 1, -1):
nums[i] = nums[i - k]
# 将临时数组中的元素复制到数组前面
for i in range(k):
nums[i] = temp[i]

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Answer 1:

前后缀分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
temp1 = [1]*n
temp2 = [1]*n
temp = 1
ans = [1]*n
for i in range(1, n):
temp *= nums[i-1]
temp1[i] = temp
temp = 1
for i in range(n-1):
temp *= nums[n-1-i]
temp2[n-2-i] = temp
for i in range(n):
ans[i] = temp1[i]*temp2[i]
return ans

73. Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
You must do it in place.

Example 1:

Answer 1:

解法一采用同等大小的矩阵来记录0的位置,然后遍历矩阵,如果某个位置是0,则将对应的行和列都置为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m = len(matrix)
n = len(matrix[0])
temp = [0]*(m*n)
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
temp[i*n+j] = 1
for i in range(m*n):
if temp[i] == 1:
M = int(i / n)
N = int(i % n)
for j in range(n):
matrix[M][j] = 0
for k in range(m):
matrix[k][N] = 0
return matrix

Answer 2:

官方解法,可读性要更强一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
row, col = [False] * m, [False] * n

for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row[i] = col[j] = True

for i in range(m):
for j in range(n):
if row[i] or col[j]:
matrix[i][j] = 0
作者:力扣官方题解


Leetcode hot100
http://jrhu0048.github.io/2025/03/12/leetcode-hot100/
作者
JR.HU
发布于
2025年3月12日
更新于
2025年3月17日
许可协议