Tag
【双层循环】【单层循环】【数组】【2024-01-23】
题目来源
解题思路
两个方法，一个是双层循环，一个是单层循环。
方法一：双层循环
思路
第一层枚举子数组的起点，第二层从起点的下一个元素开始枚举，判断接下来的字符是否满足交替子数组的条件。如是则更新长度，否则调出内层循环。
算法
class Solution {
public:
int alternatingSubarray(vector<int>& nums) {
int res = -1;
int n = nums.size();
for (int firstIndex = 0; firstIndex < n; firstIndex++) {
for (int i = firstIndex + 1; i < n; i++) {
int length = i - firstIndex + 1;
if (nums[i] - nums[firstIndex] == (length - 1) % 2) {
res = max(res, length);
} else {
break;
}
}
}
return res;
}
};
复杂度分析
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)，
n
n
n 为数组 nums 的长度。
空间复杂度：
O
(
1
)
O(1)
O(1)。
方法二：单层循环
思路
解题思路参考 教你一次性把代码写对！O(n) 分组循环（Python/Java/C++/Go/JS/Rust）。
算法
class Solution {
public:
int alternatingSubarray(vector<int> &nums) {
int ans = -1;
int i = 0, n = nums.size();
while (i < n - 1) {
if (nums[i + 1] - nums[i] != 1) {
i++; // 直接跳过
continue;
}
int i0 = i; // 记录这一组的开始位置
i += 2; // i 和 i+1 已经满足要求，从 i+2 开始判断
while (i < n && nums[i] == nums[i0] + (i - i0) % 2) {
i++;
}
// 从 i0 到 i-1 是满足题目要求的（并且无法再延长的）子数组
ans = max(ans, i - i0);
i--;
}
return ans;
}
};
复杂度分析
时间复杂度：
O
(
n
)
O(n)
O(n)，
n
n
n 为数组 nums 的长度。
空间复杂度：
O
(
1
)
O(1)
O(1)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。
最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。
原文地址:https://blog.csdn.net/weixin_54383080/article/details/135769105
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_61267.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
