哈希

1.字母异位词分组

49. 字母异位词分组

方法一：排序
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

unordered_map<string, vector<string>>​ 

主要是理解，key是排序后的字母序列，value是vector，存放了多个string

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {int n = strs.size();unordered_map<string, vector<string>> map;for (auto s : strs) {string tmp = s;sort(tmp.begin(), tmp.end());map[tmp].emplace_back(s);}vector<vector<string>> ans;for (unordered_map<string, vector<string>>::iterator it = map.begin(); it != map.end(); it++) {ans.emplace_back(it->second);}return ans;}
};

2.最长连续序列

128. 最长连续序列
重要的是思路，
1.用set去除重复数
2.找到一个序列起点最小的数num，开始在容器里while找num++是否存在，如果存在那么len++
3.怎么找到最小数，也不能说是最小数，是一个连续数种的最小数，num - 1如果存在那么他就不是连续的最小数

unordered_set<int> mp;
...
for (auto num: mp) {if (mp.count(num -1)) continue;int curnum = num;int len = 1;while (mp.count(curnum + 1)) {curnum += 1;len += 1;}longestlen = max(len, longestlen);
}

class Solution {
public:int longestConsecutive(vector<int>& nums) {int res = 0;    // 记录最长连续序列的长度unordered_set<int> num_set(nums.begin(), nums.end());   // 记录nums中的所有数值int seqLen;for(int num: num_set){// 如果当前的数是一个连续序列的起点，统计这个连续序列的长度if(!num_set.count(num - 1)){seqLen = 1;     // 连续序列的长度，初始为1while(num_set.count(++num))seqLen++;    // 不断查找连续序列，直到num的下一个数不存在于数组中res = max(res, seqLen);     // 更新最长连续序列长度}}return res;}
};

双指针

1.盛最多水的容器

11. 盛最多水的容器
两个for循环找最大值会超时，那么就有小心机，如果当前高度不比之前高，那么答案一定小于之前的值，就不必再循环了

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, ans = 0, high = 0;for (; left < height.size() - 1; left++) {if (height[left] > high) high = height[left];if (height[left] < high) continue;for (int right = left + 1; right < height.size(); right++) {int tmp = (right - left) * min(height[left], height[right]);ans = max(ans, tmp); }}return ans;}
};

正经的比较快的算法是，两端向中间移动，每次移动较小的边，计算最大值

class Solution {
public:int maxArea(vector<int>& height) {int l = 0, r = height.size() - 1;int ans = min(height[l], height[r]) * (r - l);while (l < r) {if (height[l] < height[r]) {l++;} else {r--;}ans = max(ans, (r - l) * min(height[l], height[r]));}return ans;}
};

2.和为 K 的子数组

560. 和为 K 的子数组
题目需要注意的是和为K的子数组，那么：
1.用pre[i]表示num[0]到num[i]的和
2.num[i + 1]到num[j]的和为 pre[j] - pre[i]
3.其和为k, 那么，nums[j]位置需要找到和为pre[j] - k的前缀和

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

数组

1.除自身以外数组的乘积

238. 除自身以外数组的乘积
还是想用前缀和做，计算num[i]的乘积，就是计算pre[i -1] * 后缀和
但是超时了

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {vector<int> ans;int pre = 0;for (int i = 0; i < nums.size(); i++) {if (i == 0) pre = 1;else pre *= nums[i - 1];int tmp = pre;for (int j = i + 1; j < nums.size(); j++) {tmp *= nums[j];}ans.emplace_back(tmp);}return ans;}
};

前缀和 + 后缀和
前缀和：
1.i从0开始向后
2.ans[i] = pre;
3.pre *= nums[i];
先把pre[i -1]放到ans[i]，再乘

后缀和：
1.i从size()-1开始向前
2.ans[i] *= sum2;
3.sum2 *= nums[i];
前缀乘以back[i+1]到back.end() - 1

https://blog.csdn.net/qq_43553082/article/details/118620364
vector在还没有分配任何空间时还不能像数组一样用下标形式去访问vector的（v[0]也不行）！！！否则编译通过但报运行错误runtime error！
如vector创建的时候是使用：vector<int> v;
或者vector还是[]的时候（考虑官方测试数据的输入可能为[]的情况，使用[ ]前需要判断一下是否为空）会报错！
如：v[0]=1、if(v[0])、v[0]等情况都会报错
这种情况需要先push_back()或v={1，2}等形式给其分配了空间后，才能用【】形式访问！
本题中：
vector<int> ans(nums.size());

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {vector<int> ans(nums.size());int sum = 1;for (int i = 0; i < nums.size(); i++) {ans[i] = sum;sum *= nums[i];}int sum2 = 1;for (int i = nums.size() - 1; i >= 0; i--) {ans[i] *= sum2;sum2 *= nums[i];}return ans;}
};