哈希
1. 两数之和
python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
d = defaultdict(int)
for i, x in enumerate(nums):
if target - x in d:
return [d[target - x], i]
d[x] = ijava
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
int n = nums.length;
for (int i = 0; i < n; i++) {
if (mp.containsKey(target - nums[i])) {
return new int[]{i, mp.get(target - nums[i])} ;
}
mp.put(nums[i], i);
}
}
}49. 字母异位词分组
python
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
d[''.join(sorted(s))].append(s)
return list(d.values())java
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> mp = new HashMap<>();
for (String str : strs) {
char[] s = str.toCharArray();
Arrays.sort(s);
// mp.computeIfAbsent(Arrays.toString(s), k -> new ArrayList<>()).add(str);
String key = Arrays.toString(s);
if (mp.containsKey(key)) {
mp.get(key).add(str);
} else {
List<String> tmp = new ArrayList<String>();
tmp.add(str);
mp.put(key, tmp);
}
}
return new ArrayList<List<String>>(mp.values());
}
}128. 最长连续序列
python
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
ans = 0
st = set(nums)
for num in st:
if num - 1 in st:
continue
tmp = num + 1
while tmp in st:
tmp += 1
ans = max(ans, tmp - num)
return ansjava
class Solution {
public int longestConsecutive(int[] nums) {
int ans = 0;
Set<Integer> st = new HashSet<>();
for (int num : nums) {
st.add(num); // 把 nums 转成哈希集合
}
for (int x : st) { // 遍历哈希集合
if (st.contains(x - 1)) {
continue;
}
// x 是序列的起点
int y = x + 1;
while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中
y++;
}
// 循环结束后，y-1 是最后一个在哈希集合中的数
ans = Math.max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数
}
return ans;
}
}双指针
283. 移动零
python
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = 0
for j in range(len(nums)):
if nums[j]:
nums[i], nums[j] = nums[j], nums[i]
i += 1java
class Solution {
public void moveZeroes(int[] nums) {
int left = 0, right = 0;
while (right < nums.length) {
if (nums[right] != 0) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left += 1;
}
right += 1;
}
}
}11. 盛最多水的容器
python
class Solution:
def maxArea(self, nums: List[int]) -> int:
ans, left, right = 0, 0, len(nums) - 1
while left < right:
ans = max(ans, min(nums[left], nums[right]) * (right - left))
if nums[left] >= nums[right]: right -= 1
else: left += 1
return ansjava
class Solution {
public int maxArea(int[] height) {
int ans = 0, left = 0, right = height.length - 1;
while (left < right) {
ans = Math.max(ans, Math.min(height[left], height[right]) * (right - left));
if (height[left] >= height[right]) right--;
else left++;
}
return ans;
}
}15. 三数之和
python
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n, ans = len(nums), []
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]: continue
target = -nums[i]
left, right = i + 1, n - 1
while left < right:
if nums[left] + nums[right] == target:
ans.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]: left += 1
while left < right and nums[right] == nums[right - 1]: right -= 1
left += 1
right -= 1
elif nums[left] + nums[right] < target:
left += 1
else:
right -= 1
return ansjava
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = n - 1;
while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (s == 0) {
ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
}
else if (s < 0) l++;
else r--;
}
}
return ans;
}
}42. 接雨水
python
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
st = []
for i, x in enumerate(height):
while st and x >= height[st[-1]]:
tmp = st.pop()
if not st: break
ans += (min(x, height[st[-1]]) - height[tmp]) * (i - st[-1] - 1)
st.append(i)
return ansjava
class Solution {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> st = new LinkedList<>();
for (int i = 0; i < height.length; i++) {
while (!st.isEmpty() && height[i] > height[st.peek()]) {
int tmp = st.pop();
if (st.isEmpty()) {
break;
}
ans += (Math.min(height[i], height[st.peek()]) - height[tmp]) * (i - st.peek() - 1);
}
st.push(i);
}
return ans;
}
}滑动窗口
3. 无重复字符的最长子串
python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
d = {}
left, ans = 0, 0
for right, c in enumerate(s):
if c in d:
left = max(left, d[c] + 1)
d[c] = right
ans = max(ans, right - left + 1)
return ansjava
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] cnt = new int[128];
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
++cnt[s.charAt(right)];
if (cnt[s.charAt(right)] == 1) {
ans = ans < right - left + 1 ? right - left + 1 : ans;
}
else {
while (cnt[s.charAt(right)] > 1) {
--cnt[s.charAt(left)];
++left;
}
}
}
return ans;
}
}438. 找到字符串中所有字母异位词
python
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n, m = len(s), len(p)
if n < m: return []
ans = []
sCount, pCount = [0] * 26, [0] * 26
for i in range(m):
pCount[ord(p[i]) - ord('a')] += 1
sCount[ord(s[i]) - ord('a')] += 1
if sCount == pCount:
ans.append(0)
for i in range(n - m):
sCount[ord(s[i]) - ord('a')] -= 1
sCount[ord(s[i + m]) - ord('a')] += 1
if sCount == pCount:
ans.append(i + 1)
return ansjava
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int n = s.length(), m = p.length();
if (n < m) return new ArrayList<Integer>();
List<Integer> ans = new ArrayList<Integer>();
int[] sCount = new int[26];
int[] pCount = new int[26];
for (int i = 0; i < m; i++) {
++pCount[p.charAt(i) - 'a'];
++sCount[s.charAt(i) - 'a'];
}
if (Arrays.equals(sCount, pCount)) {
ans.add(0);
}
for (int i = 0; i < n - m; i++) {
--sCount[s.charAt(i) - 'a'];
++sCount[s.charAt(i + m) - 'a'];
if (Arrays.equals(sCount, pCount)) {
ans.add(i + 1);
}
}
return ans;
}
}子串
560. 和为 K 的子数组
python
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
cnt = defaultdict(int, {0: 1})
ans = tmp = 0
for num in nums:
tmp += num
ans += cnt[tmp - k]
cnt[tmp] += 1
return ansjava
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> mp = new HashMap<>();
mp.put(0, 1);
int ans = 0, tmp = 0;
for (int num : nums) {
tmp += num;
ans += mp.getOrDefault(tmp - k, 0);
mp.put(tmp, mp.getOrDefault(tmp, 0) + 1);
}
return ans;
}
}239. 滑动窗口最大值
python
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans = []
q = deque()
for i, x in enumerate(nums):
while q and x >= nums[q[-1]]:
q.pop()
q.append(i)
while q[0] <= i - k:
q.popleft()
if i >= k - 1:
ans.append(nums[q[0]])
return ansjava
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> q = new LinkedList<>();
int[] ans = new int[nums.length - k + 1];
int j = 0;
for (int i = 0; i < nums.length; i++) {
while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) {
q.removeLast();
}
q.addLast(i);
while (q.peek() <= i - k) {
q.removeFirst();
}
if (i >= k - 1) {
ans[j] = nums[q.peek()];
j++;
}
}
return ans;
}
}76. 最小覆盖子串
python
class Solution:
def minWindow(self, s: str, t: str) -> str:
cnt = Counter(t)
need, cur = len(t), len(s)
l = 0
ans = ""
for r, c in enumerate(s):
if cnt[c] > 0: need -= 1
cnt[c] -= 1
if need == 0:
while cnt[s[l]] != 0:
cnt[s[l]] += 1
l += 1
if r - l <= cur:
cur = r - l
ans = s[l: r + 1]
cnt[s[l]] += 1
need += 1
l += 1
return ansjava
class Solution {
public String minWindow(String s, String t) {
int[] cnt = new int[128];
int need = t.length(), cur = s.length();
int l = 0;
String ans = "";
for (int i = 0; i < need; i++) {
cnt[t.charAt(i)]++;
}
for (int r = 0; r < s.length(); r++) {
if (cnt[s.charAt(r)] > 0) {
need--;
}
cnt[s.charAt(r)]--;
if (need == 0) {
while (cnt[s.charAt(l)] != 0) {
cnt[s.charAt(l)]++;
l++;
}
if (r - l <= cur) {
cur = r - l;
ans = s.substring(l, r + 1);
}
cnt[s.charAt(l)]++;
need++;
l++;
}
}
return ans;
}
}