LeetCode Hot 100

LeetCode Hot 100

1. 两数之和

思路 1：暴力枚举

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for (int i = 0; i < n - 1; i++)for (int j = i + 1; j < n; j++)if (nums[i] + nums[j] == target)return {i, j};return {-1, -1};}
};

思路 2：排序 + 双指针

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();vector<pair<int, int>> comb;for (int i = 0; i < n; i++)comb.push_back(make_pair(nums[i], i));sort(comb.begin(), comb.end(),[&](const pair<int, int>& p1, const pair<int, int>& p2) {return p1.first < p2.first;});int i = 0, j = n - 1;while (i < j) {if (comb[i].first + comb[j].first == target)return {comb[i].second, comb[j].second};else if (comb[i].first + comb[j].first > target)j--;elsei++;}return {-1, -1};}
};

思路 3：一次遍历 + 哈希

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();unordered_map<int, int> hashMap; // [num, idx]for (int i = 0; i < n; i++) {if (hashMap.find(target - nums[i]) != hashMap.end())return {hashMap[target - nums[i]], i};hashMap[nums[i]] = i;}return {-1, -1};}
};

49. 字母异位词分组

思路 1：哈希分组

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {if (strs.empty())return {};unordered_map<string, vector<string>> hashMap;for (string& s : strs) {string tmp = s;sort(tmp.begin(), tmp.end());hashMap[tmp].push_back(s);}vector<vector<string>> ans;for (auto& [tmp, vec] : hashMap)ans.push_back(vec);return ans;}
};

128. 最长连续序列

思路 1：哈希 + 单向寻找连续序列

class Solution {
public:int longestConsecutive(vector<int>& nums) {if (nums.empty())return 0;unordered_set<int> hashSet;for (int& num : nums)hashSet.insert(num);int ans = INT_MIN;for (auto& num : hashSet) {if (hashSet.find(num - 1) == hashSet.end()) {int cur = num;int cnt = 1;while (hashSet.count(cur + 1)) {cur++;cnt++;}ans = max(ans, cnt);}}return ans;}
};

思路 2：哈希 + 双向寻找连续序列

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> hash;// 把所有数字放到一个哈希表for (int& num : nums)hash.insert(num);int maxLen = 0;while (!hash.empty()) {auto cur = *(hash.begin());hash.erase(cur);int next = cur + 1, prev = cur - 1;while (hash.count(next)) {hash.erase(next);next++;}while (hash.count(prev)) {hash.erase(prev);prev--;}maxLen = max(maxLen, next - prev - 1);}return maxLen;}
};

283. 移动零

思路 1：遍历

class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size();int idx = 0;for (int i = 0; i < n; i++)if (nums[i] != 0)nums[idx++] = nums[i];while (idx < n) {nums[idx] = 0;idx++;}}
};

思路 2：双指针

class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size();// left 指向当前已经处理好的序列的尾部int left = 0;// right 指向待处理序列的头部int right = 0;while (right < n) {if (nums[right]) {swap(nums[left], nums[right]);left++;}right++;}}
};

11. 盛最多水的容器

思路 1：双指针

class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int left = 0, right = n - 1;int ans = INT_MIN;while (left < right) {int area = min(height[left], height[right]) * (right - left);ans = max(ans, area);if (height[left] < height[right])left++;elseright--;}return ans;}
};

15. 三数之和

思路 1：三重循环 + 集合去重（超时）

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();set<vector<int>> set;for (int i = 0; i < n - 2; i++)for (int j = i + 1; j < n - 1; j++)for (int k = j + 1; k < n; k++)if (nums[i] + nums[j] + nums[k] == 0) {vector<int> v = {nums[i], nums[j], nums[k]};sort(v.begin(), v.end());set.insert(v);}vector<vector<int>> ans(set.begin(), set.end());return ans;}
};

思路 2：排序 + 双指针

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();if (n < 3)return {};sort(nums.begin(), nums.end());set<vector<int>> set;for (int i = 0; i < n; i++) {int target = -nums[i];int left = i + 1, right = n - 1;while (left < right) {if (nums[left] + nums[right] > target)right--;else if (nums[left] + nums[right] < target)left++;else {vector<int> v = {nums[i], nums[left], nums[right]};set.insert(v);left++;right--;}}}vector<vector<int>> ans(set.begin(), set.end());return ans;}
};

42. 接雨水

思路 1：前后缀分解

class Solution {
public:int trap(vector<int>& height) {int n = height.size();vector<int> preMax(n);for (int i = 0; i < n; i++){if (i == 0)preMax[i] = height[i];elsepreMax[i] = max(preMax[i - 1], height[i]);}vector<int> sufMax(n);sufMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--)sufMax[i] = max(sufMax[i + 1], height[i]);int water = 0;for (int i = 0; i < n; i++)water += min(preMax[i], sufMax[i]) - height[i];return water;}
};

思路 2：相向双指针

// 相向双指针class Solution
{
public:int trap(vector<int> &height){int n = height.size();int left = 0, right = n - 1;// pre_max 表示前缀最大值，suf_max 表示后缀最大值int pre_max = 0, suf_max = 0;int sum = 0;while (left < right){// 更新前后缀最大值pre_max = max(pre_max, height[left]);suf_max = max(suf_max, height[right]);if (pre_max < suf_max){sum += pre_max - height[left];left++;}else{sum += suf_max - height[right];right--;}}return sum;}
};

思路 3：单调栈

// 单调栈class Solution
{
public:int trap(vector<int> &height){int ans = 0;stack<int> st;for (int i = 0; i < height.size(); i++){while (!st.empty() && height[i] >= height[st.top()]){int bottom_h = height[st.top()];st.pop();if (st.empty())break;int left = st.top();// 面积的高和宽int dh = min(height[left], height[i]) - bottom_h;int dw = i - left - 1;ans += dh * dw;}st.push(i);}return ans;}
};

3. 无重复字符的最长子串

思路 1：滑动窗口 + 哈希表

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.length();int maxLen = 0;unordered_set<char> hashSet;for (int left = 0, right = 0; right < n; right++) {while (hashSet.count(s[right])) {hashSet.erase(s[left]);left++;}hashSet.insert(s[right]);maxLen = max(maxLen, right - left + 1);}return maxLen;}
};

思路 2：动态规划 + 哈希表

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.length();unordered_map<char, int> dic;int res = 0, tmp = 0;for (int left, right = 0; right < n; right++) {if (dic.find(s[right]) == dic.end())left = -1;elseleft = dic.find(s[right])->second; // 获取索引 i// 更新哈希表dic[s[right]] = right;// dp[j - 1] -> dp[j]tmp = tmp < right - left ? tmp + 1 : right - left;res = max(res, tmp);}return res;}
};

438. 找到字符串中所有字母异位词

思路 1：固定长度滑动窗口 + 哈希表

class Solution {
public:vector<int> findAnagrams(string s, string p) {int sLen = s.length(), pLen = p.length();if (sLen < pLen)return {};vector<int> sCount(26, 0), pCount(26, 0);vector<int> ans;for (int i = 0; i < pLen; i++) {sCount[s[i] - 'a']++;pCount[p[i] - 'a']++;}if (sCount == pCount)ans.push_back(0);for (int i = pLen; i < sLen; i++) {sCount[s[i - pLen] - 'a']--;sCount[s[i] - 'a']++;if (sCount == pCount){// 子串开头是 i - pLen + 1ans.push_back(i - pLen + 1);}}return ans;}
};

思路 2：可变长度滑动窗口 + 哈希表

class Solution {
public:vector<int> findAnagrams(string s, string p) {int sLen = s.length(), pLen = p.length();if (sLen < pLen)return {};vector<int> sCount(26, 0), pCount(26, 0);vector<int> ans;for (int i = 0; i < pLen; i++)pCount[p[i] - 'a']++;if (sCount == pCount)ans.push_back(0);for (int left = 0, right = 0; right < sLen; right++) {sCount[s[right] - 'a']++;while (sCount[s[right] - 'a'] > pCount[s[right] - 'a']) {sCount[s[left] - 'a']--;left++;}if (right - left + 1 == pLen)ans.push_back(left);}return ans;}
};

560. 和为 K 的子数组

思路 1：二重循环枚举（超时）

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size();int count = 0;for (int start = 0; start < n; start++)for (int len = 1; len <= n - start; len++)if (accumulate(nums.begin() + start, nums.begin() + start + len,0) == k)count++;return count;}
};

思路 2：前缀和

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size();vector<int> preSum(n + 1, 0);for (int i = 1; i <= n; i++)preSum[i] = preSum[i - 1] + nums[i - 1];int count = 0;for (int i = 0; i < n; i++)for (int j = i + 1; j <= n; j++)if (preSum[j] - preSum[i] == k)count++;return count;}
};

哈希表优化：

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size();vector<int> preSum(n + 1, 0);for (int i = 1; i <= n; i++)preSum[i] = preSum[i - 1] + nums[i - 1];int count = 0;unordered_map<int, int> hashMap; // <preSum, cnt>for (int i = 0; i <= n; i++) {if (hashMap.find(preSum[i] - k) != hashMap.end())count += hashMap[preSum[i] - k];hashMap[preSum[i]]++;}return count;}
};