2026年编程兔冬令营集训第六场作业

1、双指针

2、滑动窗口

概念与核心思想
双指针：是一种通过设置两个指针（通常为数组或链表的索引）来遍历数据结构的技巧。两个指针的移动方式和条件根据具体问题而定，可用于解决多种问题，如查找、比较、合并等。
滑动窗口：是双指针的一种特殊应用形式，核心是维护一个“窗口”（即数组或字符串的连续子区间），通过动态调整窗口的左右边界（即两个指针）来寻找满足特定条件的子数组或子串。

1、这题有不同的做法。这介绍双指针。通过维护一个滑动窗口（区间），动态调整窗口的左右边界，使得窗口内数字的和与目标值进行比较，从而高效地找到所有满足条件的连续自然数段。S=[l,r]区间的总和;
如果S<M，则++l,S+=r;
如果S=M，则输出++r,S+=r;
如果S>M，则S-=l，++l
一直重复以上操作，直到l>M/2
#include<bits/stdc++.h>
using namespace std;

int main() {
    int m;
    cin >> m;
    int l = 1, r = 2;
    long long sum = l + r; // 使用 long long 避免溢出

    while (l <= m / 2) {
        if (sum == m) {
            cout << l << " " << r << endl;
            sum -= l;
            l++;
        } else if (sum < m) {
            r++;
            sum += r;
        } else {
            sum -= l;
            l++;
        }
    }
    return 0;
}
2、假设a[last]到a[i-1]都是不重复的数字，则有
a.当a[i]也是不重复的，则可以加到范围里面,last到i的数字都是不重复的；
b.如果a[i]在a[last]到a[i-1]出现过，出现的位置位j，则last=j+1，last到i的数字都是不重复的。
在b中问题就转化为如何快速的找到j的位置也就是a[i]前面出现的位置?
unordered_map可以解决这个问题。
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> mp;//记录每个数上次出现的位置 ，不需要排序 
int n,x,ans =0,last=1;
int a[1000005];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		if (mp[a[i]]){//last到i-1之间出现过a[i]，则last直接指向上次a[i]出现的位置加1 
			while(last<=mp[a[i]]){
				mp[a[last]]=0;
				++last;
			}
		}
		ans = max(ans, i-last+1);
		mp[a[i]] = i;
	}
	printf("%d",ans);
	return 0;
}
3、假设a[last]到a[i-1]都是一样的数字，则有
c.当a[i]=a[i-1]，last到i的数字都是一样的；
d.如果a[i]!=a[i-1]，则输出[last,i-1]。
#include<bits/stdc++.h>
using namespace std;
int n,x,y,ans =0,last=1;
int main(){
	scanf("%d",&n);
	scanf("%d",&y);
	for(int i=2;i<=n;++i){
		scanf("%d",&x);
		if (x!=y){
			printf("%d %d\n",last,i-1);
			last = i;
			y=x;
		}
	}
	printf("%d %d\n",last,n);
	return 0;
}
4、思考一下这题是否可以借鉴第二题的一些思路？
unordered_map<int,int> mp;来统计x出现的次数,mp[x]++或者mp[x]--
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> mp;//记录每个数的次数 
int n,k,ans =0;
int a[1000005];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		++mp[a[i]];//增加a[i]出现的次数 
	
		if (i>=k){
			if (i>k){
				--mp[a[i-k]];//减少a[i-k]出现的次数 
				//如果a[i-k]出现的次数为0，则清除a[i-k] 
				if (mp[a[i-k]]==0) mp.erase(a[i-k]);
			}
			int num = mp.size();
			ans = max(ans, num);
		}
	}
	printf("%d",ans);
	return 0;
}