行业知识
leetcode 2.27
leetcode hot 100
- 哈希
- 1.字母异位词分组
- 2.最长连续序列
- 双指针
- 1.盛最多水的容器
- 2.和为 K 的子数组
- 数组
- 1.除���身以外数组的乘积
哈希
1.字母异位词分组
49. 字母异位词分组
方法一：排序
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
unordered_map
主要是理解，key是排序后的字母序列，value是vector，存放了多个string
class Solution {public: vector groupAnagrams(vector& strs) { int n = strs.size(); unordered_map map; for (auto s : strs) { string tmp = s; sort(tmp.begin(), tmp.end()); map[tmp].emplace_back(s); } vector ans; for (unordered_map::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 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& nums) { int res = 0; // 记录最长连续序列的长度 unordered_set num_set(nums.begin(), nums.end()); // 记录nums中的所有数值 int seqLen; for(int num: num_set){ // 如果当前的数是一个连续序列的起点，统计这个连续序列的长度 if(!num_set.count(num - 1)){ seqLen = 1; // 连续序列的长度，初始为1 while(num_set.count(++num))seqLen++; // 不断查找连续序列，直到num的下一个数不存在于数组中 res = max(res, seqLen); // 更新最长连续序列长度 } } return res; }};双指针
1.盛最多水的容器
11. 盛最多水的容器
两个for循环找最大值会超时，那么就有小心机，如果当前高度不比之前高，那么答案一定小于之前的值，就不必再循环了
class Solution {public: int maxArea(vector& height) { int left = 0, ans = 0, high = 0; for (; left high) high = height[left]; if (height[left]正经的比较快的算法是，两端向中间移动，每次移动较小的边，计算最大值
class Solution {public: int maxArea(vector& height) { int l = 0, r = height.size() - 1; int ans = min(height[l], height[r]) * (r - l); while (l2.和为 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& nums, int k) { unordered_map 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 productExceptSelf(vector& nums) { vector ans; int pre = 0; for (int i = 0; i前缀和 + 后缀和
前缀和：
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 v;
或者vector还是[]的时候（考虑官方测试数据的输入可能为[]的情况，使用[ ]前需要判断一下是否为空）会报错！
如：v[0]=1、if(v[0])、v[0]等情况都会报错
这种情况需要先push_back()或v={1，2}等形式给其分配了空间后，才能用【】形式访问！
本题中：
vector ans(nums.size());
class Solution {public: vector productExceptSelf(vector& nums) { vector ans(nums.size()); int sum = 1; for (int i = 0; i = 0; i--) { ans[i] *= sum2; sum2 *= nums[i]; } return ans; }};
- 1.除���身以外数组的乘积
