leetcode 525. Contiguous Array | 525. 连续数组（Java）

红太狼 2022-09-12 08:50 159阅读 0赞

## 题目 ##

[https://leetcode.com/problems/contiguous-array/][https_leetcode.com_problems_contiguous-array]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

想到了这个题，不过和本题没什么关系，仅仅是想到了而已：  
[https://leetcode.com/problems/flip-string-to-monotone-increasing/][https_leetcode.com_problems_flip-string-to-monotone-increasing]  
以及 flip-string-to-monotone-increasing 这道题的迷之解法：

int minFlipsMonoIncr(char * s){ 
        int z = *s == '0' ? 0 : 1;
        int o = *s == '0' ? 1 : 0;
        for(s++; *s; s++){ 
            if(*s == '0'){ 
                o = (z < o ? z : o) + 1;
            }else{ 
                o = (z < o ? z : o);
                z++;
            }
        }
        return z < o ? z : o;
    }

#### 回到本题 ####

一看数据范围是 1~10000，就知道这题必须 O(n)。

先贴一下没有什么卵用的错误思路草稿：  
（错误在于，假设在0的个数少于1的个数，当前num=0的情况下，在更新的时候，你不知道应该取多少个0才合适。既不能取全部0，因为全部0不一定取的到，又不知道如果不取全部0的话，到底应该取多少，所以这个思路不可行。）  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

折腾了一个小时，打补丁，最后发现思路有结构性缺陷。于是看了答案。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 4]

class Solution { 
        public int findMaxLength(int[] nums) { 
            int diff = 0;
            HashMap<Integer, Integer> map = new HashMap<>();// (diff, index)
            map.put(0, -1);
            int max = 0;
            for (int i = 0; i < nums.length; i++) { 
                if (nums[i] == 0) diff++;
                else diff--;
                
                if (!map.containsKey(diff)) map.put(diff, i);
                else max = Math.max(max, i - map.get(diff));
            }
            return max;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 5]

[https_leetcode.com_problems_contiguous-array]: https://leetcode.com/problems/contiguous-array/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e692bda681d84218be24b4cc7dab9560.png
[https_leetcode.com_problems_flip-string-to-monotone-increasing]: https://leetcode.com/problems/flip-string-to-monotone-increasing/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/d38a79f54bd24846a50b199cc0333a51.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/43b0eb4d9045443c94848f670ca7cac6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/5889d8a1c2cc421fbfe52d471026fd77.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/55aaa3e1b6514501a173969558e1e1f8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/3287c66851734a55b0b11a7f1ddf29fd.png