# 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 it = mp.find(target - nums[i]);
if (it != mp.end()) {
return {it -> second, i};
}
mp[nums[i]] = i;
}
return {};
}
};
``````

# 2.字母异位词分组

``````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+2...x+y

``````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;
}
};
``````

# 4.移动零

``````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 ++;
}
}
};
``````

# 5.盛水最多的容器

``````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;
}
};
``````

# 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;
}
};
``````

# 7.接雨水

``````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;
}
};
``````

# 8.无重复字符的最长子串

``````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;
}
};
``````

# 9.找到字符串中所有异位词

``````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;
}
};
``````

# 10.和为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;
}
};
``````

Q.E.D.