腾讯百度阿里华为常见算法面试题TOP100(4)：双指针、哈希、滑动窗口
之前总结过字节跳动TOP50算法面试题：
字节跳动常见算法面试题top50整理_沉迷单车的追风少年-CSDN博客_字节算法面试题
目录
双指针
42.接雨水
283.移动零
11.盛最多水的容器
15.三数之和
哈希
1. 两数之和
49.字母异位词分组
128.最长连续序列
滑动窗口
3.无重复字符的最长子串
438.找到字符串中所有字母异位词
双指针
42.接雨水
用单调栈再做一遍吧……
class Solution {
public:
int trap(vector<int>& height) {
//当前柱子如果小于等于栈顶元素，说明形不成凹槽，则将当前柱子入栈；
//反之若当前柱子大于栈顶元素，说明形成了凹槽，于是将栈中小于当前柱子的元素pop出来，将凹槽的大小累加到结果中。
int ans = 0;
stack<int> sta;
for (int i = 0; i < height.size(); i++) {
while (!sta.empty() && height[i] > height[sta.top()]) {
int top = sta.top();
sta.pop();
if (sta.empty()) {
break;
}
int left = sta.top();
int w = i - left - 1;
int h = min(height[i], height[left]) - height[top];
ans += w * h;
}
sta.push(i);
}
return ans;
}
};283.移动零
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 双指针
// 左指针指向当前已经处理好的序列的尾部
// 右指针指向待处理序列的头部
// 每次交换都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变
int left = 0;
int right = 0;
while (right < nums.size()) {
if (nums[right] != 0) {
swap(nums[left], nums[right]);
left ++;
}
right ++;
}
return;
}
};11.盛最多水的容器
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int ans = 0;
while (left < right) {
int minheight = min(height[left], height[right]); //盛水取决于最短的线
ans = max(ans, (minheight * (right - left)));
if (height[left] < height[right]) { // 移动短的线
left ++;
} else {
right --;
}
}
return ans;
}
};15.三数之和
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// 排序后用双指针查找
vector<vector<int> > ans;
sort(nums.begin(), nums.end());
int left, right;
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] > 0) {
continue;
}
left = i + 1;
right = nums.size() - 1;
while (left < right) {
if ((nums[i] + nums[left] + nums[right]) == 0) {
ans.push_back({nums[i], nums[left], nums[right]});
// 去除重复元素
while (left < right && nums[left] == nums[left + 1]) {
left ++;
}
while (left < right && nums[right] == nums[right - 1]) {
right --;
}
// 移动指针
left ++;
right --;
} else if ((nums[i] + nums[left] + nums[right]) > 0) {
right --;
} else {
left ++;
}
}
// i 下标也需要去重
while (i + 1 < nums.size() && nums[i] == nums[i + 1])
i++;
}
return ans;
}
};哈希
1. 两数之和
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); i++) {
if (m.find(nums[i]) != m.end()) {
return {m[nums[i]], i};
}
m[target - nums[i]] = i;
}
return ans;
}
};49.字母异位词分组
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ans;
// 哈希表存储
unordered_map<string, vector<string> > m;
for (auto s : strs) {
string key = s;
// 排序后所有异位词存在唯一key
sort(key.begin(), key.end());
m[key].push_back(s);
}
for (auto it = m.begin(); it != m.end(); it++) {
ans.push_back(it->second);
}
return ans;
}
};128.最长连续序列
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
// 用哈希表存储是否出现过的数字
unordered_set<int> hash;
int ans = 0;
for (auto num : nums) {
hash.insert(num);
}
for (auto x : hash) {
// 如果当前数字前面没有出现过数字,则从当前位置开始查
// 因为如果前一个数字出现过, 那么他已经被查找过了
if (!hash.count(x - 1)) {
int y = x;
// 一直往后查找连续的序列
while (hash.count(y + 1)) {
y++;
}
// 维护最大的ans
ans = max(ans, y - x + 1);
}
}
return ans;
}
};滑动窗口
3.无重复字符的最长子串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 滑动窗口
int left = 0;
int right = 0;
int ans = 0;
// 记录窗口
unordered_map<char, int> windows;
while (right < s.size()) {
char c = s[right];
right ++;
windows[c] ++;
// 收缩窗口
while (windows[c] > 1) {
char d = s[left];
left ++;
windows[d] --;
}
// 维护最大ans
ans = max(right - left, ans);
}
return ans;
}
};438.找到字符串中所有字母异位词
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
// 滑动窗口
int left = 0;
int right = 0;
int count = 0;
// 当前窗口中的字符和需要凑齐的字符
unordered_map<char, int> windows, need;
// 需要凑齐的字符
for (auto c : p) {
need[c] ++;
}
while (right < s.size()) {
// 向右滑动
char c = s[right];
right ++;
// 进行窗口内数据更新
if (need.count(c)) {
windows[c] ++;
if (windows[c] == need[c]) {
count ++;
}
}
// 左侧收缩窗口
while (right - left >= p.size()) {
if (count == need.size()) {
ans.push_back(left);
}
char d = s[left];
left ++;
// 窗口内数据更新
if (need.count(d)) {
if (windows[d] == need[d]) {
count --;
}
windows[d] --;
}
}
}
return ans;
}
};