799.最长连续不重复子序列
给定一个长度为 nn 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 nn。
第二行包含 nn 个整数（均在 0∼1050∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例：
5
1 2 2 3 5
输出样例：
3
核心思路：
1.对于重复的理解
不是单纯的判断==的关系，而是多申请了一个额外的数组，充当一个hash table，把原元素当成key值，记录元素的频率。当频率大于1的时候，就是重复了.
2.对于间断的时机的理解
由于推理逻辑是具有连续性的，所以，由于前一个i到j的区间是不重复的，但是之后出现了重复。只有一种可能，那就是最新的p[i]与之前区间里面的数据重复了。即只需要“恰头”，一个循环一直丢头，直到p[i]的频率为1为止。
#include
using namespace std ;
#define read(x) scanf("%d",&x) ;
const int N = 100010 ;
int main(){
int n ; int r = 0 ; int p[N] ; int s[N] = {0} ;
read(n) ;
for(int i = 0 ,j = 0 ; i< n ;++i){
read(p[i]) ;
s[p[i]] ++ ;
while(s[p[i]] > 1) --s[p[j++]] ;
r = max(r, i-j+1) ;
}
cout<< r<< endl ;
return 0 ;
}
2007.从双倍数组中还原原数组
一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。
给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。
示例 1：
输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。
示例 2：
输入：changed = [6,3,0,1]
输出：[]
解释：changed 不是一个双倍数组。
示例 3：
输入：changed = [1]
输出：[]
解释：changed 不是一个双倍数组。
提示：
1 <= changed.length <= 105
0 <= changed[i] <= 105
class Solution {
public:
vector findOriginalArray(vector& a) {
sort(a.begin(), a.end());
int res = 0;
unordered_map mp;
vector b;
for(auto &v: a){
if(mp[v]==0){
mp[2*v]++; //只标记双倍的
b.push_back(v);
}else{
mp[v]--; //如果双倍的值也在changed数组里面，那么双倍标记就会清除掉
}
}
for(auto &[k, v]: mp){
if(v) res++; //如果有value值不是零的，说明是因为前面有值的二倍而在后面找不到，所以就冗余下来了
}
if(res) return {};
return b;
}
};
