律所网站建设国队男子接力赛,品牌包装设计,wordpress用户互通,外贸怎么做网站文章目录 Tag题目来源解题思路方法一#xff1a;双层循环方法二#xff1a;单层循环 写在最后 Tag
【双层循环】【单层循环】【数组】【2024-01-23】 题目来源
2765. 最长交替子数组 解题思路
两个方法#xff0c;一个是双层循环#xff0c;一个是单层循环。
方法一双层循环方法二单层循环 写在最后 Tag
【双层循环】【单层循环】【数组】【2024-01-23】 题目来源
2765. 最长交替子数组 解题思路
两个方法一个是双层循环一个是单层循环。
方法一双层循环
思路
第一层枚举子数组的起点第二层从起点的下一个元素开始枚举判断接下来的字符是否满足交替子数组的条件。如是则更新长度否则调出内层循环。
算法
class Solution {
public:int alternatingSubarray(vectorint 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(vectorint 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 和 i1 已经满足要求从 i2 开始判断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)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
