蓝桥杯历届试题-连号区间数-题解（耗时较少）（C++代码）

解题思路:

其实题目很简单，外层的双重遍历是肯定少不了的，问题就是你在遍历之后进行判断的方法：

错误示范：用sort排序，这样耗时太长，会超时。

其实对于这道题目因为他的数是连续的，所以比较简单，我们可以利用这一点：

只要我们做到：最大值-最小值+1=i - j+1（即你要判断的区间长度）

（1）耗时较多的：用max( )和min( ),来查找，可以通过，我用了这里其他同学的耗时 61.

（2）耗时较少：其实很简单，因为我们的外层的双重遍历肯定是少不了的，我们可以在这个遍历的过程中找到max

和min（代码在下面）。

注意事项: 注意不要超时

核心代码：（这里耗时31,其实这里还可以进行一些合并)

for(int i=0;i<n;i++){
		int min=arr[i];
		int max=arr[i];
		for(int j=i;j<n;j++){
			if(i == j) {
				ans++;
				continue; 
			}
			else{
				if(arr[j]>max) max=arr[j];
				if(arr[j]<min) min=arr[j];
				if(max-min+1==j-i+1) ans++;
			}
		
		}
	}

核心代码2：

for(int i=0;i<n;i++){
		int min=arr[i];
		int max=arr[i];
		for(int j=i;j<n;j++){
			
			if(arr[j]>max) max=arr[j];
			if(arr[j]<min) min=arr[j];
			if(max-min+1==j-i+1) ans++;
				
			}
		
		}
	}

完整参考代码:

#include<iostream>
using namespace std;

int n;
int arr[50000];
int ans=0;

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	
	for(int i=0;i<n;i++){
		int min=arr[i];
		int max=arr[i];
		for(int j=i;j<n;j++){
			
			if(arr[j]>max) max=arr[j];
			if(arr[j]<min) min=arr[j];
			if(max-min+1==j-i+1) ans++;
		
		}
	}
	cout<<ans;
	return 0;
}