## 哈希 ### [1.两数之和](https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked) - 时间复杂度: $ O(n) $ - 空间复杂度: $ O(n) $, $n$ 为 $nums$ 中不重复的元素数量 ```cpp class Solution { public: vector twoSum(vector& nums, int target) { unordered_map vis; for (int i = 0; i < nums.size(); ++ i) { if (vis.find(target - nums[i]) != vis.end()) { return {vis[target - nums[i]], i}; } if (vis.find(nums[i]) == vis.end()) { vis[nums[i]] = i; } } return {}; } }; ``` ### [2.字母异位词分组](https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked) - 时间复杂度: $ O(nklogk) $, $n$ 为 $strs$ 的长度, $k$ 为每个字符串的长度 - 空间复杂度: $ O(nk) $ ```cpp class Solution { public: vector> groupAnagrams(vector& strs) { map> dict; string t; for (string s : strs) { t = s; sort(s.begin(), s.end()); dict[s].emplace_back(t); } vector> ans; for (auto [k, v] : dict) { ans.emplace_back(v); } return ans; } }; ``` ### [128. 最长连续序列](https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked) - 时间复杂度: $ O(n) $, $n$ 为 $nums$ 的长度 - 空间复杂度: $ O(n) $ ```cpp class Solution { public: int longestConsecutive(vector& nums) { int ans = 0; unordered_set st(nums.begin(), nums.end()); for (int x : st) { if (st.contains(x - 1)) { continue; } int y = x + 1; while (st.contains(y)) ++y; ans = max(ans, y - x); } return ans; } }; ``` ## 双指针 ### [283. 移动零](https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked) - 时间复杂度: $ O(n) $, $n$ 为 $nums$ 的长度 - 空间复杂度: $ O(1) $ ```cpp class Solution { public: void moveZeroes(vector& nums) { int cnt = 0, n = nums.size(); for (int i = 0; i < n; ++ i) { if (nums[i] == 0) cnt += 1; else nums[i - cnt] = nums[i]; } for (int i = 0; i < cnt; ++ i) { nums[n - i - 1] = 0; } } }; ``` ### [11. 盛最多水的容器](https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked) > 双指针，两边向中间，高的不动，低的向中间遍历 - 时间复杂度: $ O(n) $, $n$ 为 $height$ 的长度 - 空间复杂度: $ O(1) $ ```cpp class Solution { public: int maxArea(vector& height) { int n = height.size(), ans = 0, l = 0, r = n - 1; while (l < r) { ans = max(ans, (r - l) * min(height[l], height[r])); height[l] < height[r] ? ++ l : -- r; } return ans; } }; ``` ### [15. 三数之和](https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked) - 时间复杂度: $ O(n^2) $, $n$ 为 $nums$ 的长度 - 空间复杂度: $ O(logn) $ ```cpp class Solution { public: vector> threeSum(vector& nums) { sort(nums.begin(), nums.end()); int n = nums.size(); vector> ans; for (int i = 0; i < n - 2; ++ i) { // 去重 if (i && nums[i] == nums[i - 1]) continue; // 减少次数 if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break; // 减少次数 if (nums[i] + nums[n - 1] + nums[n - 2] < 0) continue; // 有序数组的两者之和 int l = i + 1, r = n - 1; while (l < r) { int s = nums[i] + nums[l] + nums[r]; if (s > 0) -- r; else if (s < 0) ++ l; else { ans.push_back({nums[i], nums[l], nums[r]}); // 去重 for (++ l; l < r && nums[l] == nums[l - 1];++ l); for (-- r; r > l && nums[r] == nums[r + 1]; -- r); } } } return ans; } }; ``` ### [3. 无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked) 经典双指针题 - 时间复杂度: $ O(n) $, $n$ 为 $s$ 的长度 - 空间复杂度: $ O(n) $ ```cpp class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map cnt; int n = s.size(); int ans = 0; for (int i = 0, j = 0; j < n; ++ j) { cnt[s[j]]++; while (cnt[s[j]] > 1 && i < j) cnt[s[i++]]--; ans = max(ans, j - i + 1); } return ans; } }; ``` ## 子串 ### [1.和为 K 的子数组](https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked) 前缀和 + 哈希表 - 时间复杂度: $ O(n) $, $n$ 为 $s$ 的长度 - 空间复杂度: $ O(n) $ ```cpp class Solution { public: int subarraySum(vector& nums, int k) { int n = nums.size(); vector arr(n + 1, 0); for (int i = 1; i <= n; ++ i) { arr[i] = arr[i - 1] + nums[i - 1]; } int ans = 0; unordered_map cnt; for (int i = 0; i <= n; ++ i) { if (cnt[arr[i] - k] != 0) { ans += cnt[arr[i] - k]; } cnt[arr[i]] ++; } return ans; } }; ``` ## 普通数组 ### [1.最大子数组和](https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked) > 每次更新以当前位置为尾部的最大策略 - 时间复杂度: $ O(n) $, $n$ 为 $nums$ 的长度 - 空间复杂度: $ O(1) $ ```cpp class Solution { public: int maxSubArray(vector& nums) { int pre_sum = 0, ans = -10100; int n = nums.size(); for (int i = 0; i < n; ++ i) { pre_sum = max(pre_sum + nums[i], nums[i]); ans = max(ans, pre_sum); } return ans; } }; ``` ### [2. 合并区间](https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked) - 时间复杂度: $ O(NlogN) $, $N$ 为 $intervals$ 的长度 - 空间复杂度: $ O(logN) $ ```cpp class Solution { public: vector> merge(vector>& intervals) { int n = intervals.size(); sort(intervals.begin(), intervals.end()); vector> ans; for (auto& v : intervals) { if (!ans.empty() && ans.back()[1] >= v[0]) { ans.back()[1] = max(ans.back()[1], v[1]); } else { ans.push_back({v[0], v[1]}); } } return ans; } }; ``` ### [3.轮转数组](https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked) - 时间复杂度: $ O(n) $, $n$ 为 $nums$ 的长度 - 空间复杂度: $ O(1) $ ```cpp class Solution { public: void reverse(vector& nums, int l, int r) { int i = l, j = r; while (i <= j) { swap(nums[i], nums[j]); ++ i, -- j; } } void rotate(vector& nums, int k) { int n = nums.size(); k %= n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } }; ``` ### [4. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked) - 时间复杂度: $ O(n) $, $n$ 为 $nums$ 的长度 - 空间复杂度: $ O(1) $ ```cpp class Solution { public: vector productExceptSelf(vector& nums) { int n = nums.size(); vector ans(n, 1); // 前缀 for (int i = 1; i < n; ++ i) { ans[i] = ans[i - 1] * nums[i - 1]; } int suffix = 1; // 后缀 * 前缀 for (int i = n - 2; i >= 0; -- i) { suffix *= nums[i + 1]; ans[i] *= suffix; } return ans; } }; ```

leetcode-hot100