双指针算法-day14（分组循环）

1.最长奇偶子数组

题目

解析

• 分组循环模板：

•  简单来说：
  • 第一步：指针遍历找到满足条件的开头下标，并用 start = i 记录开头；
  • 第二步：指针不断右移寻找满足条件的最长子数组；
  • 第三步：更新答案；
• 时间复杂度：O(n)，空间复杂度：O(1)；

代码

class Solution {
public:int longestAlternatingSubarray(vector<int>& nums, int threshold) {// 时间复杂度：O(n)// 空间复杂度：O(1)int n = nums.size();int ans = 0;int i = 0;while(i < n){if(nums[i] > threshold || nums[i] % 2){i ++;// 直接跳过continue;}int start = i ++;// 找到了满足条件的开头下标while(i < n && nums[i] <= threshold && nums[i] % 2 != nums[i - 1] % 2){i ++;// 寻找满足条件最长子数组}ans = max(ans,i - start);// (start,i - 1) 均满足条件}return ans;}
};

2.连续字符

题目

解析

• 同理可得

代码

class Solution {
public:int maxPower(string s) {// 时间复杂度：O(n)// 空间复杂度：O(1)int n = s.size();int ans = 0;int i = 0;while(i < n){int start = i ++;while(i < n && s[i] == s[i - 1]){i ++;}ans = max(ans,i - start);}return ans;}
};

3.哪种连续子字符串更长

题目

解析

• 同理可得

代码

class Solution {int count(string s,char k){int n = s.size();int ans = 0;int i = 0;while(i < n){if(s[i] != k){i ++;continue;}int start = i ++;while(i < n && s[i] == k){i ++;}ans = max(ans,i - start);}return ans;}public:bool checkZeroOnes(string s) {// 时间复杂度：O(n)// 空间复杂度：O(1)return count(s,'1') > count(s,'0');}
};

4.找出长度为 K 的特殊子字符串

题目

解析

• 同理可得

代码

class Solution {
public:bool hasSpecialSubstring(string s, int k) {// 时间复杂度：O(n)// 空间复杂度：O(1)int n = s.size();int i = 0;while(i < n){int start = i ++;while(i < n && s[i] == s[i - 1]){i ++;}if(i - start == k) return true;}return false;}
};

5.删除字符使字符串变好

题目

解析

• 同理可得

代码

class Solution {
public:string makeFancyString(string s) {// 时间复杂度：O(n)// 空间复杂度：O(1)int n = s.size();string ans;int i = 0;while(i < n){int start = i ++;while(i < n && s[i] == s[i - 1]){i ++;}if(i - start <= 2) ans += s.substr(start,i - start);else ans += s.substr(start,2);}return ans;}
};

6.最长连续递增序列

题目

解析

• 同理可得

代码

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {// 时间复杂度：O(n)// 空间复杂度：O(1)int n = nums.size();int ans = 1;int i = 0;while(i < n){int start = i ++;while(i < n && nums[i] > nums[i - 1]){i ++;}ans = max(ans,i - start);}return ans;}
};

7.最长湍流子数组

题目

解析

• 题目要求：相邻数字单调性不断翻转；
• 判断条件：(arr[i - 1] - arr[i]) * (arr[i] - arr[i + 1]) < 0；
• 注意：i + 1 号元素也满足条件，所以 ans += i - start + 1 注意加 1；

代码

class Solution {typedef long long LL;
public:int maxTurbulenceSize(vector<int>& arr) {// 时间复杂度：O(n)// 空间复杂度：O(1)int n = arr.size();int ans = 1;int i = 0;while(i < n - 1){ // 判断要用到后面一个元素if(arr[i] == arr[i + 1]){i ++;continue;// 重复元素跳过}int start = i ++;while(i < n - 1 && (LL)(arr[i - 1] - arr[i]) * (arr[i] - arr[i + 1]) < 0){i ++;}ans = max(ans,i - start + 1);// i + 1 号元素也满足}return ans;}
};