当前位置: 首页> 文旅> 旅游 > 连续数组 ---- 前缀和

连续数组 ---- 前缀和

时间:2025/7/11 7:45:02来源:https://blog.csdn.net/m0_73992740/article/details/139234974 浏览次数:0次

题目链接

题目:

分析:

  • 如果我们直接做这道题, 有点麻烦
  • 如果我们将所有的0都变成1, 那么找到数量相同的0和1的最长连续子数组, 就是找最长连续子数组的和为0, 那么就和之前的题目<找到和为k的子数组>有点像, 需要用前缀和+哈希表来完成
  • 在[0,i-1]区间找到前缀和= sum[i] - 0, 即sum[i]
  • 那么哈希表中, 我们要存的就不是前缀和 和 个数了, 而应该存的是 前缀和sum 和 此时的下标i
  • 什么时候将前缀和存在哈希表中? 使用完之后, 即更新完结果之后
  • 如果有重复的sum 和i , 只保留原哈希表中存的i, 无需更新, 因为题目中要的是最长的子数组, 先存进去的下标一定是更靠前的, 子数组更长
  • 默认前缀和为0的情况, 即[0,i] 的和为0, 那么我们应该在-1的位置找前缀和, 所以要添加(0,-1)
  • 题目中要返回数组的长度, 长度应该怎么算呢?

代码:

class Solution {public int findMaxLength(int[] nums) {Map<Integer, Integer> hash = new HashMap<>();hash.put(0, -1);int sum = 0;//前缀和int ret = 0;// 最长的长度for (int i = 0; i < nums.length; i++) {sum += (nums[i] == 0 ? -1 : 1);//无需真的将数组中的0改成1, 只需在此判断即可if (hash.containsKey(sum)) {ret = Math.max(ret, i - hash.get(sum));} else {hash.put(sum, i);}}return ret;}
}

关键字:连续数组 ---- 前缀和

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: