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应该就能看懂了


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