鱼C论坛

 找回密码
 立即注册
查看: 2456|回复: 1

[技术交流] C++刷LeetCode(525. 连续数组)【前缀和】

[复制链接]
发表于 2021-6-3 10:43:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 糖逗 于 2021-6-3 16:40 编辑

题目描述:
  1. 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。

  2.  

  3. 示例 1:

  4. 输入: nums = [0,1]
  5. 输出: 2
  6. 说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
  7. 示例 2:

  8. 输入: nums = [0,1,0]
  9. 输出: 2
  10. 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
  11.  

  12. 提示:

  13. 1 <= nums.length <= 105
  14. nums[i] 不是 0 就是 1

复制代码


  1. class Solution {
  2. public:
  3.     int findMaxLength(vector<int>& nums) {
  4.         //前缀和
  5.         map<int, int> store = {{0,-1}};
  6.         int cur = 0, res = 0;
  7.         for(int i = 0; i < nums.size(); i++){
  8.             nums[i] == 0 ? cur-- : cur++;
  9.             if(store.count(cur)){
  10.                 res = max(res, i - store[cur]);
  11.             }else{
  12.                 store[cur] = i;
  13.             }  
  14.         }
  15.         return res;
  16.     }
  17. };
复制代码

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2021-6-4 09:25:34 | 显示全部楼层
这里1和0的权重作用是意义的,所以是从头开始的最长就是最长。如果权重不一样可能要考虑从中间开始的最长
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 04:33

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表