解法1：
最暴力的方法，存每个数字出现的次数，排序之后，扫一遍，对于每个数字，看它后面连续的k-1个是否都存在。
耗时：404ms
class Solution {
public:
bool isPossibleDivide(vector<int>& nums, int k) {
map<int,int> mp;
for(int v:nums){
mp[v]++;
}
sort(nums.begin(),nums.end());
bool ans=true;
for(int v:nums){
if(!mp[v]){
continue;
}else{
for(int i=1;i<k;i++){
if(!mp[v+i]){
ans=false;
break;
}
}
if(!ans){
break;
}else{
for(int i=0;i<k;i++){
mp[v+i]--;
}
}
}
}
return ans;
}
};
解法2：
debug了1个小时...果然不会写代码了。
用k个指针来指向当前正确的(连续)k个数，然后每次尝试往后移1位，判断是否有不满足的。
耗时：108ms
class Solution {
public:
bool isPossibleDivide(vector<int>& nums, int k) {
int len=nums.size();
cout << len << endl;
if(len%k){
return false;
}
int vis[len+5]={0};
sort(nums.begin(),nums.end());
int tag[k+5]={-1};
tag[0]=0;
vis[tag[0]]=1;
for(int i=1;i<k;i++){
for(int j=tag[i-1]+1;j<len;j++){
if(nums[j]==nums[tag[i-1]]+1){
tag[i]=j;
break;
}
}
if(tag[i]==-1){
return false;
}
vis[tag[i]]=1;
}
while(true){
tag[0]++;
while(vis[tag[0]] && tag[0]+1<len){
tag[0]++;
}
if(vis[tag[0]]){
break;
}
vis[tag[0]]=1;
for(int i=1;i<k;i++){
tag[i]=max(tag[i],tag[i-1])+1;
while(tag[i]+1<len && (nums[tag[i]]!=nums[tag[i-1]]+1 || vis[tag[i]])){
tag[i]++;
}
if(nums[tag[i]]!=nums[tag[i-1]]+1 || vis[tag[i]]){
return false;
}
vis[tag[i]]=1;
}
}
for(int i=0;i<len;i++){
if(!vis[i]){
return false;
}
}
return true;
}
};