一、哈希

1.兩數之和

1. 兩數之和

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

2.字母異位詞分組

49. 字母異位詞分組

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vector<string>> res;if (strs.size() == 0)return res;unordered_map<string,vector<string>> mp;for (auto t : strs) {string str = t;sort(str.begin(),str.end());mp[str].push_back(t);}for (auto it = mp.begin(); it != mp.end(); it ++) {res.push_back(it -> second);}return res;}
};

3.最長連續序列

128. 最長連續序列

class Solution {
public:int longestConsecutive(vector<int>& nums) {if (nums.size() == 0) return 0;unordered_set<int> mp;for (const int&nun : nums) {mp.insert(num);}	int res = 0;for (auto ch : mp) {if (!mp.count(ch - 1)) {int curNum = ch;int curStreak = 1;while (mp.count(curNum + 1)) {curNum += 1;curStreak += 1;}res = max(res,curStreak);}}return res;}};

二、雙指針

4. 移動零

283. 移動零

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

5.盛最多水的容器

11. 盛最多水的容器

class Solution {
public:int maxArea(vector<int>& height) {int i = 0, j = height.size() - 1;int res = 0;while (i < j) {res = height[i] < height[j] ?max(res,(j - i) * height[i ++]) :max(res,(j - i) * height[j --]) ;}return res;}
};

6.三數之和

15. 三數之和

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;if (nums.size() == 0) return res;sort(nums.begin(),nums.end());if (nums[0] > 0) return res;for (int k = 0; k < nums.size() - 2; k ++) {if (k > 0 && nums[k] == nums[k - 1]) continue;int i = k + 1,j = nums.size() - 1;while (i < j) {int sum = nums[k] + nums[i] + nums[j];if (sum < 0) {while (i < j && nums[i] == nums[++i]) ;}else if(sum > 0) {while (i < j && nums[j] == nums[--j]) ;}else {res.push_back(vector<int>{nums[k], nums[i], nums[j]});while (i < j && nums[i] == nums[++i]) ;while (i < j && nums[j] == nums[--j]) ;}}}return res;}
};

7.接雨水

42. 接雨水

三、滑動窗口

8.無重復字符的最長子串

3. 無重復字符的最長子串

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char,int> windows;int left = 0,right = 0;int res = 0;int n = s.size();while (right < n) {char c = s[right];right ++;windows[c] ++;while (windows[c] > 1) {char d = s[left];left ++;windows[d] --;}res = max(res,right - left);}return res;}
};

9.找到字符串中所有字母異位詞

438. 找到字符串中所有字母異位詞

class Solution {
public:vector<int> findAnagrams(string s, string p) {unordered_map<char,int> need,window;for (char c : p) need[c] ++;int left = 0,right = 0;int vaild = 0;vector<int> res;while (right < s.size()) {char c = s[right];right ++;if (need.count(c)) { // 如果需要這個元素window[c] ++; // 窗口中的值 ++if (window[c] == need[c]) { // 如果窗口中的值和需要的值相等vaild++; // 有效值++{}}}while (right - left >= p.size()) { // 當現在的左右差大于子串p的大小if (vaild == need.size()) // 如果有效值 == needres.push_back(left); //  加入char d = s[left]; // 縮小窗口left ++;if (need.count(d)) {if (window[d] == need[d])vaild--;window[d]--;}}}return res;}
};

四、子串

10.和為 K 的子數組

560. 和為 K 的子數組

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> mp;mp[0] = 1;int count = 0,pre = 0;for (auto x : nums) {pre += x;if (mp.find(pre - k) != mp.end()) {count += mp[pre - k];}mp[pre] ++;}return count;}
};