Every day a Leetcode
题目来源:3254. 长度为 K 的子数组的能量值 I
解法1:暴力
遍历数组 nums 中的每个长度为 k 的子数组,判断子数组中的所有相邻元素是否满足后一个元素与前一个元素之差等于 1,如果满足则子数组的能量值等于子数组的最后一个元素,否则子数组的能量值等于 −1。
代码:
/** @lc app=leetcode.cn id=3254 lang=cpp** [3254] 长度为 K 的子数组的能量值 I*/// @lc code=start
class Solution
{
public:vector<int> resultsArray(vector<int> &nums, int k){int n = nums.size();vector<int> ans;for (int i = 0; i <= n - k; i++){bool flag = true;for (int j = i + 1; j < i + k && flag; j++)if (nums[j] != nums[j - 1] + 1)flag = false;if (flag)ans.push_back(nums[i + k - 1]);elseans.push_back(-1);}return ans;}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(n * k),其中 n 是数组 nums 的长度,k 是给定的正整数。子数组的数量是 n−k+1,对于每个子数组计算能量值的时间是 O(k),因此时间复杂度是 O(n * k)。
空间复杂度:O(1)。注意返回值不计入空间复杂度。