CD 2 最長的可整合子數組的長度

題目描述

先給出可整合數組的定義：如果一個數組在排序之後，每相鄰兩個數的差的絕對值都為1，或者該數組長度為1，則該數組為可整合數組。例如，[5, 3, 4, 6, 2]排序後為[2, 3, 4, 5, 6]，符合每相鄰兩個數差的絕對值都為1，是以這個數組為可整合數組

給定一個數組arr, 請傳回其中最大可整合子數組的長度。例如，[5, 5, 3, 2, 6, 4, 3]的最大可整合子數組為[5, 3, 2, 6, 4]，是以請傳回5

[要求]

時間複雜度為O(n^2)O(n

2

)，空間複雜度為O(n)O(n)

輸入描述:

第一行一個整數N，表示數組長度

第二行N個整數，分别表示數組内的元素

輸出描述:

輸出一個整數，表示最大可整合子數組的長度

示例1

輸入

複制

7

5 5 3 2 6 4 3

輸出

複制

5

思路：用unordered_set，來判斷一個數是否重複出現過，如果沒有那麼用MAX-MIN==j-i 表示這一段是可整合數組，更新長度

#include<iostream>
 #include<stdio.h>
 #include<vector>
 #include<climits>
 #include<unordered_set>
 using namespace std;
 
 vector<int> vi;
 
 int main()
 {
 	int n;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)
	 {
	 	int x;
	 	scanf("%d",&x);
	 	vi.push_back(x);
	 }
 	  
 	unordered_set<int> un_st;
 	int res=-1;
 	for(int i=0;i<n;i++)
	 {
	 	int MAX= INT_MIN ,MIN=INT_MAX;
	 	for(int j=i;j<n;j++)
		 {
		 	if( un_st.find(vi[j]) != un_st.end()  )//有重複元素 
			 	break;
			un_st.insert(vi[j]);
			MAX= max( MAX, vi[j] );
			MIN= min( MIN, vi[j] ); 
			if( MAX-MIN==j-i  )
			{
			     res=max(res,j-i+1);	
			}
		 }
		un_st.clear();
	 }
	 
	 cout<<res<<endl;
 	return 0;
 }