LeetCode热题100：双指针
摘要
移动零
给定一个数组 nums，编写一个函数将所有 0
移动到数组的末尾，同时保持非零元素的相对顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
void moveZeroes(vector<int>& nums) {
int zeros = 0;
int k = 0;
for(auto it : nums){
if(it != 0){
nums[k++] = it;
}else{
zeros++;
}
}
while(zeros--) nums[k++] = 0;
}
};
|
盛最多水的容器
给定一个长度为 n 的整数数组 height 。有
n 条垂线，第 i 条线的两个端点是
(i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int maxArea(vector<int>& height) {
int ans = 0;
int l = 0;
int r = height.size()-1;
while(l != r){
ans = max(ans, min(height[r], height[l])*(r-l));
if(height[l] < height[r]){
l++;
}else{
r--;
}
}
return ans;
}
};
|
三数之和
给你一个整数数组 nums ，判断是否存在三元组
[nums[i], nums[j], nums[k]] 满足
i != j、i != k 且 j != k
，同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0 且不重复的三元组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int> > ans;
sort(nums.begin(), nums.end());
for(int i = 0 ; i+2 < nums.size() ; i ++){
if(i != 0 && nums[i] == nums[i-1]) continue;
if(nums[i] + nums[i+1] + nums[i+2] > 0) break;
if(nums[i] + nums[nums.size()-2] + nums[nums.size()-1] < 0) continue;
int l = i+1;
int r = nums.size()-1;
while(l < r){
if(nums[l] + nums[r] == -nums[i]){
ans.push_back({nums[i], nums[l], nums[r]});
for (l++; l < r && nums[l] == nums[l - 1]; l++);
for (r--; r > l && nums[r] == nums[r + 1]; r--);
}else if(nums[l] + nums[r] > -nums[i]){
r--;
}else if(nums[l] + nums[r] < -nums[i]){
l++;
}
}
}
return ans;
}
};
|
接雨水
给定 n 个非负整数表示每个宽度为 1
的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
1）前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int trap(vector<int>& h) {
vector<int > pre(h.size()), back(h.size());
int ans = 0;
pre[0] = h[0];
for(int i = 1 ; i < h.size() ; i ++){
pre[i] = max(pre[i-1], h[i]);
}
back[h.size()-1] = h[height.size()-1];
for(int i = h.size()-2 ; i >= 0 ; i --){
back[i] = max(back[i+1], h[i]);
}
for(int i = 1 ; i < height.size()-1 ; i ++){
int mi = min(pre[i-1], back[i+1]);
ans += max(mi - height[i], 0);
}
return ans;
}
};
|
2）双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int trap(vector<int> & h) {
int l = 0, r = h.size()-1;
int lm = h[l], rm = h[r];
int ans = 0;
while(l < r){
if(h[l] < h[r]){
ans += max(0, lm - h[l]);
l++;
lm = max(lm, h[l]);
}else{
ans += max(0, rm - h[r]);
r--;
rm = max(rm, h[r]);
}
}
return ans;
}
};
|
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的
最长 子串 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> mp;
if (s.length() == 0)
return 0;
int ans = 1;
int l = 0, r = 1;
mp[s[l]] = 1;
while (r < s.size()) {
mp[s[r]]++;
while (mp[s[r]] >= 2) {
mp[s[l]]--;
l++;
}
ans = max(r - l + 1, ans);
r++;
}
return ans;
}
};
|
找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s
中所有 p 的 异位词
的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if(s.size() < p.size()) return {};
vector<int > cnt(27), pcnt(27), ans;
for(auto it : p){
pcnt[it - 'a']++;
}
for(int i = 0 ; i < p.size() ; i ++){
cnt[s[i] - 'a']++;
}
if(cnt == pcnt) ans = {0};
for(int i = p.size() ; i < s.size() ; i ++){
cnt[s[i-p.size()] - 'a']--;
cnt[s[i] -'a']++;
if(cnt == pcnt){
ans.push_back(i-p.size()+1);
}
}
return ans;
}
};
|
最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回
s 中涵盖 t 所有字符的最小子串。如果
s 中不存在涵盖 t
所有字符的子串，则返回空字符串 "" 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<bits/stdc++.h>
using namespace std;
class Solution {
public:
string minWindow(string s, string t) {
if(s.size() < t.size()) return "";
vector<int > v(256, 0);
for(auto it : t) v[it]++;
string ans = "";
int l = 0, mi = INT_MAX, cnt = t.size();
for(int r = 0 ; r < s.size() ; r ++){
if(v[s[r]] > 0) cnt--;
v[s[r]]--;
while(v[s[l]] < 0){
v[s[l]]++; l++;
}
if(cnt == 0){
if(r-l+1 < mi){
mi = r-l+1;
ans = s.substr(l, r-l+1);
}
v[s[l]]++;
l++;
cnt++;
}
}
return ans;
}
};
|