题目链接2982. 找出出现至少三次的最长特殊子字符串 II中等算法原理解法二分查找98ms击败51.14%时间复杂度O(Nlogn)核心思路我们可以通过顺序表数组把各个字母的各个连续段长度存起来通过二分查找找到符合的子串长度①目标变量子串长度②目标条件s中出现≥3次的最长特殊子字符串长度③转换逻辑当前子串长度mid下能否有≥3次的最长特殊子字符串具体步骤①确定区间边界left0rights的长度②确定二分模型由于要找最长的特殊子串长度找最长用最右端点模型如果当前mid长度下不能凑出≥3次的最长特殊子字符串长度说明mid太大了应该向左调整变小点以便适应更多次数也就是说呈负相关单调子串长度↑ 目标条件符合度↓③check方法设计1.如果mid为0说明一定为不能凑出特殊子串直接返回false2.遍历每个小写字母看看每段的长度能否凑出来遍历过程中如果遇到空表直接跳过如果这段比mid小就跳过找下一段比mid大就累加这段的贡献量由于特殊子串连续贡献量长度1-mid比如mid3该段5那么这段可以是123、234、345共3段正好是51-33对的上如果凑不出就返回true向左调整midJava代码class Solution { private static ListInteger[] groups; public int maximumLength(String ss) { //统计每个字符的连续长度 char[] sss.toCharArray(); groupsnew ArrayList[26]; Arrays.setAll(groups,_-new ArrayList()); int count0; for(int i0;is.length;i){ count; if(i1s.length||s[i]!s[i1]){ //把这一段的长度添加进去 groups[s[i]-a].add(count); //重新计数 count0; } } //二分框架 int left0,rights.length; while(leftright){ int midleft(right-left1)/2; if(check(mid)) rightmid-1; else leftmid; } //如果所有都不能凑出就返回-1 return check(left)?-1:left; } //判断能否存在某个字符能凑出至少3个长度为mid的相同子串 //若不能凑出则返回true向左调整mid private boolean check(int mid){ if(mid0) return true; //遍历每个小写字母看看每段的长度能否凑出来 for(ListInteger word:groups){ //该字符无连续段直接跳过 if(word.isEmpty()) continue; //统计该字符当前段能凑出mid长度子串的总数 int sum0; for(int l:word){ if(lmid) continue; suml1-mid;//累加该段的贡献量 if(sum3) return false; } } return true; } }