如何实现C++查找数组全正元素最长连续区间的首尾索引
问题描述
现有一个长度为m的整数数组days[m],需要获取满足以下条件的最长连续区间的首、尾元素索引:该区间内的所有int型元素值均大于0。
参考示例
输入数组:
days[m] = {1,2,2,3,3,5}
输出结果:1 3
尝试编写的代码
int max = 0,ind,ind2,db; for(int i = 0;i < m;i++){ if(days[i] > 0){ db = 1; int j = i; while(days[j] > 0){ db++; j++; } if(db > max){ max = db; ind = i; ind2 = i+db; } } } cout<<ind<<" "<<ind2<<endl;
代码逻辑漏洞
- 数组越界风险:内层while循环没有对下标
j做边界判断,当连续正元素延伸到数组末尾时,会读取数组外的非法内存,触发未定义行为。 - 索引计算错误:连续段长度计数存在偏移,
db初始值设为1,每遍历一个正元素就自增一次,最终得到的长度值比实际连续正段的真实长度多1,计算出的尾索引ind2会偏离正确位置,无法匹配示例输出。 - 冗余遍历问题:外层循环会重复扫描已经走过的连续正段,整体运行时间复杂度为O(m²),数据量较大时效率很低。
- 无边界兜底:
ind和ind2没有初始化默认值,当数组中不存在任何大于0的元素时,最终输出的是未初始化的随机内存值。
优化修正版本
// 设置兜底值,无有效正区间时输出-1做标识 int max_len = 0, ind = -1, ind2 = -1; int i = 0; while (i < m) { if (days[i] > 0) { int start = i; // 扫描连续正段,同步校验数组下标边界 while (i < m && days[i] > 0) { i++; } int current_len = i - start; // 匹配最长区间的索引更新逻辑 if (current_len > max_len) { max_len = current_len; ind = start; ind2 = i - 1; // 循环退出时i已落在区间边界外,回退1位即为真实尾索引 } } else { // 非正元素直接跳过,不做重复扫描 i++; } } cout << ind << " " << ind2 << endl;
内容的提问来源于stack exchange,提问作者NNDR
相关产品推荐
相关产品推荐

