1.两数之和
题解：
创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target-x，将 x 插入到哈希表中，即可保证不会重复匹配。
时间复杂度：O(n)
空间复杂度：O(n)
代码：
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 it = mp.find(target - nums[i]);
if (it != mp.end()) {
return {it -> second, i};
}
mp[nums[i]] = i;
}
return {};
}
};
2.字母异位词分组
题解：
对每个单词进行计数，将单词的出现次数转化为哈希表的“键”，将单词作为“值”进行统计。
时间复杂度：O(nk)
空间复杂度：O(nk)
代码：
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ans;
unordered_map<string, vector<string>> mp;
for (auto s : strs) {
string cnt(26, '0');
for (auto ch : s) {
cnt[ch - 'a'] += 1;
}
mp[cnt].push_back(s);
}
for(auto i : mp) {
ans.push_back(i.second);
}
return ans;
}
};
3.最长连续序列
题解：
将数字都存入一个集合中，对于每个数，我们需要知道它最长的连续长度是多少。并且我们需要优化数字的查询过程。
对于 x 而言，其连续的序列为：
那么下一次对于 x+1 而言，无需继续统计。
故优化过程：每次枚举的数一定是在集合中不存在 x-1 的，即第一次枚举的数字。如果出现则跳过。
每次循环中，维护最长的长度即可。
代码：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> st;
int ans = 0;
for (auto i : nums) {
st.insert(i);
}
for (auto num : st) {
if (!st.count(num - 1)) {
int curnum = num;
int cnt = 1;
while(st.count(curnum + 1)) {
curnum += 1;
cnt ++;
}
ans = max(ans, cnt);
}
}
return ans;
}
};
时间复杂度：O(n)
空间复杂度：O(n)
4.移动零
题解：
采用双指针的思想，l 设置为处理完序列的尾部，r 设置为待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
代码：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int l = 0, r = 0;
int n = nums.size();
while(r < n) {
if (nums[r]) {
swap(nums[l], nums[r]);
l ++;
}
r ++;
}
}
};
时间复杂度：O(n)
空间复杂度：O(1)
5.盛水最多的容器
题解：
采用双指针的思想，l 设置为左端点，r 设置为右端点。
维护的值为：min(h[l],h[r])*dis，比较两个指针所指值的大小，较小值移动。
代码：
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int ans = 0;
while(l < r) {
ans = max(ans, min(height[l], height[r]) * (r - l));
if (height[l] < height[r])
l ++;
else
r --;
}
return ans;
}
};
时间复杂度：O(n)
空间复杂度：O(1)
6.三数之和
题解：
先将数组进行排序。
遍历排序后的数组：
- 若 nums[i]>0 则后面不可能有三个数加和等于 0，直接返回结果。
- 跳过重复元素
- 令左指针为 l=i+1，右指针为 r=len-1 ，当 l<r 时，统计区间 l-r 与 nums[i] 和为 0 的答案。
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
int len = nums.size();
if (len < 3) return ans;
sort(nums.begin(), nums.end());
for (int i = 0; i < len - 2; i ++) {
if (nums[i] > 0) continue;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = len - 1;
while(l < r) {
int v = nums[i] + nums[l] + nums[r];
if (v == 0) {
ans.push_back({nums[i], nums[l], nums[r]});
while(l < r && nums[l] == nums[l + 1]) l ++;
while(l < r && nums[r] == nums[r - 1]) r --;
l ++;
r --;
}
else if (v < 0) l ++;
else if (v > 0) r --;
}
}
return ans;
}
};
时间复杂度：O(n^2)
空间复杂度：O(1)
7.接雨水
题解：
采用单调栈的思想：
维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组中的元素递减。
从左往右遍历数组，遍历到下标 i 时，如果栈内有两个元素，记栈顶元素为 top ，其下一个元素为 down ，
则一定有 h[top] \ge h[down] 。如果此时 h[i] > h[top]，说明可以接雨水，维护每个区间答案 (min(h[i],h[down])-h[top])*(i-down-1)。
代码：
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
int ans = 0;
for (int i = 0; i < height.size(); i ++) {
while (!st.empty() && height[st.top()] < height[i]) {
int topValue = height[st.top()];
st.pop();
if (st.empty()) break;
int down = st.top();
ans += (min(height[i], height[down]) - topValue) * (i - down - 1);
}
st.push(i);
}
return ans;
}
};
时间复杂度：O(n)
空间复杂度：O(n)
8.无重复字符的最长子串
题解：
用一个哈希表记录字符出现重复的位置，用 i 更新应该到达的位置，即当下次再遇到该字母时，将 i 调整到该字母下一个位置的地方。同时更新长度。
代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<int, int> mp;
int i = 0, ans = 0;
for (int j = 0; j < s.size(); j ++) {
i = max(i, mp[s[j]]);
mp[s[j]] = j + 1;
ans = max(ans, j - i + 1);
}
return ans;
}
};
时间复杂度：O(n)
空间复杂度：O(n)
9.找到字符串中所有异位词
题解：
我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护每种字母的数量；当每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。
代码：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
int slen = s.size();
int plen = p.size();
if (slen < plen) {
return ans;
}
vector<int> vs(26);
vector<int> vp(26);
for (int i = 0; i < plen; i ++) {
vs[s[i] - 'a'] ++;
vp[p[i] - 'a'] ++;
}
if (vs == vp) {
ans.push_back(0);
}
for (int i = plen; i < slen; i ++) {
vs[s[i] - 'a'] ++;
vs[s[i - plen] - 'a'] --;
if (vs == vp) {
ans.push_back(i - plen + 1);
}
}
return ans;
}
};
时间复杂度：O(n)
空间复杂度：O(n)
10.和为k的子数组
题解：
记录前缀和 pre[i] ，表示从数组起始位置到第 i 个位置的元素之和。那么对于任意的两个下标 i 和 j（i < j） ，如果 pre[j] - pre[i-1] = k ，即从第 i 个位置到第 j 个位置的元素之和等于 k 。
通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中，我们检查是否存在 pre[j] - k 的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为 k ，我们将对应的次数累加到结果中。
代码：
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int pre = 0;
int cnt = 0;
for (int i = 0; i < nums.size(); i ++) {
pre += nums[i];
if (mp.find(pre - k) != mp.end()) {
cnt += mp[pre - k];
}
mp[pre] ++;
}
return cnt;
}
};
时间复杂度：O(n)
空间复杂度：O(n)
