一、适用场景
对于一个数组,要做多次判断条件相同的处理
二、核心思想
一般分为外层循环和内层循环,两个循环用于处理不同的事情
1.外层循环用于做准备工作和内层循环后的统计工作(例如求最大值)
2.内层循环用于遍历数组
时间复杂度为O(n),因为中间的变量 " i " 是一直在加,没有减小过
模板:
int n = len(nums)//首先确定数字的长度 int i = 0//定义一个循环变量 while(i < n)//外层循环 { int start = i//定义一个记录开始位置的变量 while i < n and ...://内层循环,符合条件就继续 i++ }
三、实际运用
1.LeetCode2760最长奇偶子数组
给你一个下标从 0 开始的整数数组 nums
和一个整数 threshold
。
请你从 nums
的子数组中找出以下标 l
开头、下标 r
结尾 (0 <= L <= R < nums.length)
且满足以下条件的 最长子数组 :
nums[L] % 2 == 0
- 对于范围
[L, R - 1]
内的所有下标i
,nums[i] % 2 != nums[i + 1] % 2
- 对于范围
[L, R]
内的所有下标i
,nums[i] <= threshold
以整数形式返回满足题目要求的最长子数组的长度。
分析一下,该问题需要我们去找子数组,即需要遍历,并且在遍历的时候是有条件限制的,那么这个时候我们就可以用分组循环。
对于外层循环我们只需要一个变量" i "既可,然后就是我们要看是要在内层循环判断的。
因为我们要记录一个开始的位置,那么我们就要在外层循环判断是否满足nums[L] % 2 == 0 和 nums[i] <= threshold
然后就是内层循环,需要判断的条件为 nums[i] % 2 != nums[i + 1] % 2 和 nums[i] <= threshold
在内层循环完之后用ans来记录不断记录最大值
int ans = 0, n = nums.size(), i = 0; while(i < n){ if(nums[i] % 2 != 0 || nums[i] > threshold) { i++; continue; } int start = i;//当我们找到第一个符合条件的时候就记录下来 i++;//本题需要i++,从下一个开始判断 while(i < n && nums[i] <= threshold && nums[i] % 2 != nums[i - 1] % 2) { i++; } // i - start表示在内层循环中找到的最大的 ans = std::max(ans, i - start); } return ans;
参考:https://leetcode.cn/problems/longest-even-odd-subarray-with-threshold/solutions/2528771/jiao-ni-yi-ci-xing-ba-dai-ma-xie-dui-on-zuspx/
标签:nums,int,内层,++,循环,分组,数组 From: https://www.cnblogs.com/linx000/p/17835802.html