通过快慢指针减少重复遍历。
双指针
782. 避嫌抢劫
小镇沿街分布（可以理解为都在数轴上），有 n 家银行（位置以数轴的坐标表示，金额表示可以被抢走的金额）。
两个绑匪试图分别抢劫一个银行，为了让警方多奔波他们商定选择的两个银行距离不小于 d。
请问，符合约定的情况下他们能抢到的总金额最大是多少。
输入格式
输入包含 n+1 行。
第一行包含两个整数 n 和 d，分别表示银行的数量和约定的距离。
接下来 n 行，每行包含两个整数 a 和 b，分别表示坐标和金额。
输出格式
输出一个数字表示可以获得的最大金额。
数据范围
1≤n≤2×105,
1≤d,a,b≤108
注意：数据中保证至少存在两个银行之间的距离不小于 d。
输入样例：
6 3
1 1
3 5
4 8
6 4
10 3
11 2
输出样例：
11
思路：
对每个银行按照坐标从小到大排序，然后双指针算法从前往后遍历
对于一个特定的i，假设j指向i之后的第一个和i相隔大于d的位置，那么j及j之后的银行都是可以被抢劫的，此时我们从j即j之后的银行中挑一家钱数最多的银行抢劫，受益最大，即：答案应该更新为：$res = max(res, a[i].y + M)$, 其中M的表达式：$M = max(a[k].y), k = j, j + 1, … ,n -1$
如果我们对于每一个i，都要遍历找j及j之后的钱数最多的银行，那么时间复杂度为$O(n^2)$,会超时
所以我们可以开一个“后缀最大值”数组b,其中b[j]表示：j及j之后的银行中钱数的最大值。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 200010;
int n, d;
PII a[N];
int b[N];
int main()
{
cin >> n >> d;
for (int i = 0; i < n; i ++ )cin >> a[i].x >> a[i].y;
int res = 0;
sort(a, a + n);
int bm = 0;//behind_max
for(int i = n - 1; i >= 0; i --){
bm = max(bm, a[i].y);
b[i] = bm;
}
for(int i = 0, j = 1; i < n; i ++){
while(j < n && a[j].x - a[i].x < d)j ++;
if(j >= n)break;
res = max(res, a[i].y + b[j]);
}
cout << res << endl;
return 0;
}
61. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
假设字符串中只包含从 a 到 z 的字符。
数据范围
输入字符串长度 [0,1000]。
样例
输入："abcabc"
输出：3
思路：
- 用哈希表存储两个指针之间的每个字母出现的次数
- 每次把j向后移动一个，同时检查最后一个字母出现的次数，若大于1，则把i往后移，直到最后一个字母出现的次数为1.
- 以后指针为标准进行遍历
代码：
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {
unordered_map<char,int> hash;
int res = 0;
for(int i = 0,j = 0;j < s.size();j ++){
if(++hash[s[j]] > 1){
//就像j对前面的i说，你跟我中间有个人跟我重复了！你赶紧给我找出来踢出去！
//i也不知道哪个人重复了，就逐个往后找，每退一步就问一下j，现在还有重复吗
//j如果说没有了，那j就可以继续往后了，j要说还有，i就只能继续往后退
while(i < j){
hash[s[i ++]] --;
if(hash[s[j]] == 1)break;
}
}
res = max(res,j - i + 1);
}
return res;
}
};
76. 和为S的连续正数序列
输入一个非负整数 S，打印出所有和为 S 的连续正数序列（至少含有两个数）。
例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15,所以结果打印出 3 个连续序列 1∼5、4∼6 和 7∼8。
数据范围
0≤S≤1000
样例
输入：15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
思路：
s中存储：以i开头的，总和不超过目标值S的，最长的连续子数组的和。
i,j具有单调性：当i向后移的时候，由于总和减少，j一定不会向前移。
以前指针i为标准进行遍历
数字和的问题也可以联想前缀和！
代码：
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int>> res;
for(int i = 1, j = 1, s = 1;i <= sum/2; i ++){
while(s < sum)s += ++j;
if(s == sum && j > i){
vector<int> line;
for(int k = i;k <= j; k ++)line.push_back(k);
res.push_back(line);
}
s -= i;
}
return res;
}
};
77. 翻转单词顺序
输入一个英文句子，单词之间用一个空格隔开，且句首和句尾没有多余空格。
翻转句子中单词的顺序，但单词内字符的顺序不变。
为简单起见，标点符号和普通字母一样处理。
例如输入字符串"I am a student."，则输出"student. a am I"。
数据范围
输入字符串长度 、[0,1000]。
样例
输入："I am a student."
输出："student. a am I"
思路：
- 首先反转整个串，然后再逐个反转每个单词。
- 注意reverse函数反转单词：reverse(单词的第一个字母，单词后面的空格)
代码:
class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(),s.end());
for(int i = 0; i < s.size(); i ++){
int j = i;
while(j < s.size() && s[j] != ' ')j ++;
reverse(s.begin() + i, s.begin() + j);
i = j;
}
return s;
}
};
双指针+子数组
3801. 最佳连续子数组
标签：双指针、子数组
给定一个长度为 n 的数组 a1,a2,…,an。
请你找到其中的最佳连续子数组。
最佳连续子数组需满足：
- 子数组内各元素的算术平均数（即所有元素之和除以元素个数）尽可能大。
- 满足条件 1 的前提下，子数组的长度尽可能长。
输出最佳连续子数组的长度。
分析：
子区间长度平均值最大值：就是最大的数
等于最大值的元素有多个，并且相邻，则这个最大值子区间的长度就是所求长度。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, t;
int a[N];
int main()
{
cin >> t;
while(t -- ){
int n;
cin >> n;
int mx = 0;
for(int i = 0; i < n; i ++){
cin >> a[i];
mx = max(mx, a[i]);
}
int res = 0;
for(int i = 0; i < n; i ++){
if(a[i] == mx){
int j = i + 1;
while(j < n && a[j] == a[i])j ++;
res = max(res, j - i);
i = j - 1;
}
}
cout << res << endl;
}
return 0;
}
总结：
双指针、子数组问题，用i从前往后遍历，当i遍历到符合条件的时候，进入if语句：出现j，j = i + 1，当退出if语句的时候,i = j - 1:
for(int i = 0; i < n;i ++){
if(a[i] ...){
int j = i + 1;
while(j < n && a[j] ..)j ++ ...;
i = j - 1;
}
}
同样，如下题：
2074. 倒计数
艾弗里有一个由 N 个正整数构成的数组。
数组中的第 i 个整数是 Ai。
如果一个连续的子数组的长度为 m，并且按顺序包含整数 m,m−1,m−2,…,2,1，则称它为 m 倒计数。
例如，[3,2,1] 是 3 倒计数。
请帮助艾弗里计算她的数组中有多少个 K 倒计数。
例如，输入：
12 3//长度12的数组里，有几个3倒计数？
1 2 3 7 9 3 2 1 8 3 2 1
输出：
2
解答：
cin >> n >> k;
for(int i = 0; i < n; i ++){
cin >> a[i];
}
for(int i = 0; i < n; i ++){
if(a[i] == k){
int j = i + 1;
int k_ = k - 1;
while(j < n && a[j] == k_ && k_){
k_ --, j ++;
if(k_ == 0){
res ++;
break;
}
}
i = j - 1;
}
}
cout << res << endl;
双指针+前缀和
1922. 懒惰的牛
题目大意：
在一个数轴上，若干点上有草堆，问在某个固定长的区域内，草堆的最大数量是多少
思路：
求某个区间内的和，我们可以联想到：双指针（滑动窗口）算法、前缀和算法、差分算法
代码：
双指针：
以后指针i为基准
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
int n, m;
PII q[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )cin >> q[i].y >> q[i].x;
sort(q, q + n);
int res = 0, sum = 0;
for (int i = 0, j = 0; i < n; i ++ ){
//i向后移
sum += q[i].y;
//当第i堆草和第j堆草的间隔距离大于2*m时，将j向后移动，同时将sum减去j原来的草堆数量
while(q[i].x - q[j].x > 2 * m) sum -= q[j ++].y;
res = max(res, sum);
}
cout << res << endl;
return 0;
}
前缀和：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010; // x 的范围
int n, k;
int s[N];
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i ++ ){
int x, c;
cin >> c >> x;
s[x + 1] += c; //算前缀和的时候，数组下标从1开始
}
for(int i = 1; i < N; i ++)s[i] += s[i - 1];
int res = -1;
for(int i = 1; i < N; i ++){
int l = max(1, i - k), r = min(i + k, N - 1);
res = max(res, s[r] - s[l - 1]);
}
cout << res << endl;
return 0;
}
差分：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 1e6+10;
map<int,int> b;//构造差分数组,原数组每个位置初始为0,有草的位置x可以影响到x-k和x+k范围内的点,
//相当于给[x-k,x+k]范围内的点都加上了草的数量
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
b[y-k]+=x,b[y+k+1]-=x;
}
int res=0,sum=0;
for(auto x:b)
{
sum+=x.second;
res=max(res,sum);
}
cout<<res<<endl;
return 0;
}
102. 最佳牛围栏
农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛，其数量不会少于 1 头，也不会超过 2000 头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 N 和 F，数据间用空格隔开。
接下来 N 行，每行输入一个整数，第i+1 行输入的整数代表第 i 片区域内包含的牛的数目。
输出格式
输出一个整数，表示平均值的最大值乘以 1000 再 向下取整 之后得到的结果。
数据范围
1≤N≤100000
1≤F≤N
输入样例：
10 6
6
4
2
10
3
8
5
9
4
1
输出样例：
6500
思路：
- 由于平均值的最大值具有二段性：小于等于最大值的可能出现，大于最大值的都不可能出现，因此可以用二分法
- 二分的check(avg)函数：检查是否存在一个区间，其平均值大于avg。
- 某个区间的平均值大于avg，相当于区间内的所有数都-avg，然后看总和是否大于0.
- 区间和的问题，用前缀和。
- 是否存在区间[i, j]，区间和大于0，sum[j] - sum[i] >= 0,相当于sum[j] >= sum[i]是否有解，那么我们可以让sum[i]尽可能的小，可以用一个变量来存储sum[i]在遍历过程中的最小值。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, f;
int a[N];
double sum[N];
bool check(double avg){
for (int i = 1; i <= n; i ++ )sum[i] = sum[i - 1] + a[i] - avg;
double mi = 0;
for(int i = 0, j = f; j <= n; i ++, j ++)
{
mi = min(mi, sum[i]);
if(sum[j] >= mi)return true;
}
return false;
}
int main()
{
cin >> n >> f;
for (int i = 1; i <= n; i ++ ){
cin >> a[i];
}
double l = 0, r = 2000;
while(r - l > 1e-5){
double mid = (l + r) / 2;
if(check(mid))l = mid;
else r = mid;
}
cout << int(r * 1000) << endl;
return 0;
}
1528. 火星购物
在火星购物是一个完全不同的体验。
火星人用被链子连在一起的钻石付款，每颗钻石都有一定的价值。
付款时，只能在链条的某一位置上切割一次，然后一些钻石就会一个接着一个的从链条上脱落。
一旦钻石脱离链条，就不能在穿回去。
例如，如果我们有一个钻石链条，上面有 8 颗钻石，价值分别为 3,2,1,5,4,6,8,7 元，而我们需要支付的价格为 15 元。
我们有三种选择：
- 在 4 和 6 之间剪断链条，然后取走前 5 颗钻石，价值为 3+2+1+5+4=15。
- 在 5 之前或 6 之后剪断链条，然后取走第 4∼6 颗钻石，价值为 5+4+6=15。
- 在 8 之前剪断链条，然后取走后 2 颗钻石，价值为 8+7=15。
现在给定钻石链条上钻石的价值以及顾客需要支付的价钱，请你帮助顾客确定他有多少种选择方案。
如果无法恰好凑出顾客需要支付的确切金额，那就凑出足够支付的情况下的最少金额，从而避免钻石浪费。
输入格式
第一行包含两个整数 N 和 M，分别表示链条上的钻石数量以及顾客需要支付的金额。
第二行包含 N 个整数，D1,D2,…,DN，表示钻石的价值。
输出格式
每行输出一种可行方案，具体格式为 i-j，表示 Di+…+Dj=M
如果方案不唯一，则按照 i 递增的顺序输出所有方案。
如果无法准确凑出 M，仍然输出 i-j，表示 Di+…+Dj>M 并且 Di+…+Dj−M的值最小。
如果方案不唯一，则按照 i递增的顺序输出所有方案。
数据范围
1≤N≤105
1≤M≤108
1≤Di≤103
∑Di≥M
输入样例1：
16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13
输出样例1：
1-5
4-6
7-8
11-11
输入样例2：
5 13
2 4 5 7 9
输出样例2：
2-4
4-5
非前缀和做法：
- s中存储的是：以i开头的，j结尾的区间和
- 注意，第二次循环的时候要先将s归零！！！
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int a[N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
int s = 0;
int mins = 1e9;
bool flag = false;//false为无精确解
for(int i = 1, j = 0; j <= n && i <= n;s -= a[i ++]){
while(s < m){
s += a[++ j];
if(j > n)break;
}
if(s == m){
cout << i << '-' << j << endl;
flag = true;
}if(s > m){
mins = min(mins, s);
}
}
if(!flag){
s = 0;
for(int i = 1, j = 0; j <= n && i <= n;s -= a[i ++]){
while(s < m){
s += a[++ j];
if(j > n)break;
}
if(s == mins){
cout << i << '-' << j << endl;
}
}
}
return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com
