HOT 100

本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

哈希 ​

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] = i
java
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 ans
java
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 += 1
java
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 ans
java
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 ans
java
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 ans
java
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 ans
java
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 ans
java
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 ans
java
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 ans
java
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 ans
java
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;
    }
}

不同数组 ​

53. 最大子数组和 ​

56. 合并区间 ​

189. 旋转数组 ​

238. 除自身以外数组的乘积 ​

41. 缺失的第一个正数 ​

矩阵 ​

73. 矩阵置零 ​

54. 螺旋矩阵 ​

48. 旋转图像 ​

240. 搜索二维矩阵 II ​

链表 ​

160. 相交链表 ​

206. 反转链表 ​

234. 回文链表 ​

141. 环形链表 ​

142. 环形链表 II ​

21. 合并两个有序链表 ​

2. 两数相加 ​

19. 删除链表的倒数第 N 个节点 ​

24. 两两交换链表中的节点 ​

25. K 个一组翻转链表 ​

138. 复制带随机指针的链表 ​

148. 排序链表 ​

23. 合并 K 个升序链表 ​

146. LRU 缓存机制 ​

二叉树 ​

94. 二叉树的中序遍历 ​

104. 二叉树的最大深度 ​

226. 翻转二叉树 ​

101. 对称二叉树 ​

543. 二叉树的直径 ​

102. 二叉树的层序遍历 ​

108. 将有序数组转换为二叉搜索树 ​

98. 验证二叉搜索树 ​

230. 二叉搜索树中第 K 小的元素 ​

199. 二叉树的右视图 ​

114. 二叉树展开为链表 ​

105. 从前序与中序遍历序列构造二叉树 ​

437. 路径总和 III ​

236. 二叉树的最近公共祖先 ​

124. 二叉树中的最大路径和 ​

图论 ​

200. 岛屿数量 ​

994. 腐烂的橘子 ​

207. 课程表 ​

208. 实现 Trie (前缀树) ​

回溯 ​

46. 全排列 ​

78. 子集 ​

17. 电话号码的字母组合 ​

39. 组合总和 ​

22. 括号生成 ​

79. 单词搜索 ​

131. 分割回文串 ​

51. N 皇后 ​

二分查找 ​

35. 搜索插入位置 ​

74. 搜索二维矩阵 ​

34. 在排序数组中查找元素的第一个和最后一个位置 ​

33. 搜索旋转排序数组 ​

153. 寻找旋转排序数组中的最小值 ​

4. 寻找两个正序数组的中位数 ​

栈 ​

20. 有效的括号 ​

155. 最小栈 ​

394. 字符串解码 ​

739. 每日温度 ​

84. 柱状图中最大的矩形 ​

堆 ​

215. 数组中的第 K 个最大元素 ​

347. 前 K 个高频元素 ​

295. 数据流的中位数 ​

贪心 ​

121. 买卖股票的最佳时机 ​

55. 跳跃游戏 ​

45. 跳跃游戏 II ​

763. 划分字母区间 ​

动态规划 ​

70. 爬楼梯 ​

118. 杨辉三角 ​

198. 打家劫舍 ​

279. 完全平方数 ​

322. 零钱兑换 ​

139. 单词拆分 ​

300. 最长递增子序列 ​

152. 乘积最大子数组 ​

416. 分割等和子集 ​

32. 最长有效括号 ​

多维动态规划 ​

62. 不同路径 ​

64. 最小路径和 ​

5. 最长回文子串 ​

1143. 最长公共子序列 ​

72. 编辑距离 ​

技巧 ​

136. 只出现一次的数字 ​

169. 多数元素 ​

75. 颜色分类 ​

31. 下一个排列 ​

287. 寻找重复数 ​

Common Resources for Materials Calculation