[leetcode每日一题] 3254. 长度为 K 的子数组的能量值 I

If_you_love

比较暴力......

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n=nums.size();
        vector <int> results(n-k+1,-1);
        for (int i=0;i<n-k+1;i++)
        {
            bool jud=true;
            for (int j=0;j<k;j++)
            {
                if(nums[i+j]!=nums[i]+j)
                {
                    jud=false;
                    break;
                }
            }
            if(jud)
            {
                results[i]=nums[i+k-1];
            }
        }
        return results;
    }
};

时间复杂度：O(N*K)；空间复杂度：O(N)

yyyyye

前缀和解法
时间复杂度：$O(n)$
空间复杂度：$O(n)$

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        vector<int> prefix, ret;
        int n = nums.size();
        prefix.push_back(0);
        for(int i = 0; i < n - 1; i++)
        {
            prefix.push_back(prefix[i] + (nums[i] + 1 == nums[i + 1]));
        }
        for(int i = k - 1; i < n; i++)
        {
            ret.push_back(prefix[i] - prefix[i - k + 1] == (k - 1) ? nums[i] : -1);
        }
        return ret;
    }
};

发表情包召唤

依次判断然后把所得值或-1作为新元素添加在result末尾

public:
    vector<int> resultsArray(vector<int>& nums, int k) {
int n=nums.size();
        vector<int> results;
        for(int i=0;i<n-k+1;i++)
        {int f=1;
            for(int j=i;j<i+k-1;j++)
            {
                if(nums[j+1]-nums[j]!=1)
                {f=0;break;}
            }
            if(f)
                results.push_back(nums[i+k-1]);
            else results.push_back(-1);
        }
        return results;
    }
};```

Zero_canyon

解法大同小异

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int len = nums.size();
        vector<int>results;
        for(int i = 0;i <= len - k;i++)
        {
            int kk = 1;
            for(int j = 0;j < k;j++)
            {
                if(nums[i]+j != nums[i+j])
                {kk=0;break;}
            }
            if(kk)results.push_back(nums[i+k-1]);
            else results.push_back(-1);
        }
        return results;
    }
};

ssssshi

依次建立长度为k的子数组后对子数组遍历判断

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
    vector<int> rA;
    vector<int>arr;
    int n=nums.size();
    for(int i=0;i<=n-k;i++)
    {
        arr.assign(nums.begin()+i,nums.begin()+i+k);
        int max=arr.at(0),t=1;
        for(int i1=0;i1<k-1;i1++)
        {
            if(arr.at(i1)-arr.at(i1+1)!=-1)t=0;
            if(arr.at(i1+1)>max)max=arr.at(i1+1);
        }
        if(t==1)rA.push_back(max);
        else rA.push_back(-1);
    }
    return rA;
    }
};

wszyh

开一个长度为n-k+1的数组s并全部赋值为-1，然后找符合条件的数替换相应s数组中的数

public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int m=nums.size();
        int cnt;
        vector<int>s(m-k+1,-1);
        for(int i=0;i<m-k+1;i++){
            cnt=1;
            for(int i1=i;i1<i+k-1;i1++){
                if(nums[i1]+1!=nums[i1+1]){
                    cnt=0;
                    break;
                }
            }
            if(cnt) s[i]=nums[i+k-1];
        }
        return s;
    }
};

tjp

思路和大家差不多，在每一个长度为K的子数组中判断有没有后一项减前一项不等于1

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n = nums.size();
        int cnt = 0;
        vector<int> ans(n - k + 1, -1);
        for (int i = 0; i <= n - k; i++) {
            bool valid = true;
            for (int j = i + 1; j < i + k; j++) {
                if (nums[j] - nums[j - 1] != 1) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                ans[i] = nums[i + k - 1];
            }
        }
        return ans;
    }
};

ygxdsh

时间复杂度：O(n)
空间复杂度：O(n)
遍历数组过程中记录当前满足题目条件的最大长度，
若大于等于题目所需的k，则最大值就是当前遍历到的最后一位（因为条件要满足递增）
长度不够说明不满足条件，也就是-1

vector<int> resultsArray(vector<int>& nums, int k) {
        vector<int> a;
        int s=1;
        if(k==1) return nums;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]==nums[i-1]+1) s++;
            else
            {
                s=1;
            }
            if(i>=k-1) 
            {
                if(s>=k) a.push_back(nums[i]);
                else a.push_back(-1);
            }
        }
        return a;
    }

xujingyuan

初学：用了malloc动态分配空间，否则在栈上分配空间，函数返回时，内存可能被回收，是指针指向无效内存；然后正常循环，寻找符合条件的数组，在新数组上填上最大值或-1；最后设置returnSize的值，将结果数组的大小传递回调用者，否则会输出一个空壳。最后返回指向最终数组的指针a 。（difficult）

int* resultsArray(int* nums, int numsSize, int k, int* returnSize) {
    int isok = 1;
    //*a是指针，指向存储的内存空间
    int* a = (int*)malloc((numsSize - k + 1) * sizeof(int));
//动态分配空间，存储大小为(numsSize - k + 1) * sizeof(int)的数组
    int b = 0;
    for (int i = 0; i <= numsSize - k; i++) {
        isok = 1;//每次先假设符合条件
        for (int j = i; j < i + k - 1; j++) {
            if (nums[j] + 1!= nums[j + 1]) {
                isok = 0;
                break;
            }
        }
        if (!isok) {
            a[b++] = -1;
        } else {
            a[b++] = nums[i + k - 1];
        }
    }
    *returnSize = numsSize - k + 1;//非常重要，如果没有就只能输出数组壳；作用是传递数组真实大小
    return a;
}

RiVER

暴力解法之后模仿✌前缀和的答案

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        vector<int> ret,res;
        ret.push_back(0);
        for(int i=0;i<nums.size()-1;i++)
        {
            ret.push_back(ret[i]+(nums[i]+1==nums[i+1]));
        }
        for(int i=k-1;i<ret.size();i++)
        {
            if(ret[i]-ret[i-k+1]==k-1) res.push_back(nums[i]);
            else res.push_back(-1);
        }
        return res;
    }
};

Future

public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n=nums.size(),sum=0,j;
        vector<int>res(n-k+1,-1);
        for(int i=0;i<=n-k;i++)
        {
            sum=0;
            for(j=i;j<i+k-1;j++)
            {
                sum+=(nums[j+1]-nums[j]==1);
            }
            if(sum==k-1)
            {
                res[i]=nums[j];
            }
        }
        return res;
    }
};
卡点