leetcode-525- 间断数组

<!–more–>

[题目形容]

 给定一个二进制数组 nums , 找到含有雷同数量的 0 和 1 的最长间断子数组，并返回该子数组的长度。示例 1: 


输出: nums = [0,1]
输入: 2
阐明: [0, 1] 是具备雷同数量 0 和 1 的最长间断子数组。示例 2: 


输出: nums = [0,1,0]
输入: 2
阐明: [0, 1] (或 [1, 0]) 是具备雷同数量 0 和 1 的最长间断子数组。提醒：1 <= nums.length <= 105 
 nums[i] 不是 0 就是 1 

 Related Topics 哈希表 
 👍 293 👎 0

[题目链接]

leetcode 题目链接

[github 地址]

代码链接

[思路介绍]

思路一：暴力法（这种办法没什么意义，遍历所有子数组）

工夫复杂度 (O(n^2^))

思路二：hash 表

• 因为数组中只有 0 1 两个元素，当子元素长度为 n（n 为正偶数）时，子数组和为（n/2）
• 所以能够把 0 换成 -1 这样 子数组和即为 0, 题意转化成了求间断子数组和为 0 的最大长度子数组
• 最近做的两道题都有这种思维，通过前缀和求间断区间
• 相干题目链接 leetcode-523- 间断子数组和
• 每日一题系列
• 也就是说间断子数组长度则能够通过前缀和的差值来判断
• 首先定义一个 prefix[] 数组 prefix[i] = nums[0] +……+ nums[i]
• nums[i] +……+ nums[j] = prefix[j] – prefix[i-1]
• 如果只是这样计算每一个子数组的和其实和暴力法没有区别甚至是多了 O(n) 的工夫复杂度
• 能够依据题目含意得出，指标是求出 prefix[j] – prefix[i]== 0 的时候 j 与 i 的最大差值
• 也就是说须要求得使 prefix[j] 与 prefix[i] 相等状况 j 与 i 差值最大
• 因而能够思考引入 hashmap 进行计算，将 prefix[i] 的值作为 key 存入 hashmap 并记录以后坐标为 value
  每次求出前缀和的时候判断求 Math.max(j-i)

 public int findMaxLength(int[] nums) {
            int n = nums.length,max = 0;
            Map<Integer,Integer> map = new HashMap<>();
            int[] prefix = new int[n];
            prefix[0] = (nums[0] == 0 ? -1 : 1);
            map.put(prefix[0],0);
            // 求前缀和数组
            for (int i = 1; i < n; i++) {prefix[i] = prefix[i - 1] + (nums[i] == 0 ? -1 : 1);
                // 以后前缀和曾经满足，则进入计算范畴
                if (prefix[i] == 0){max = Math.max(i+1,max);
                }
                if (map.containsKey(prefix[i])){max = Math.max(i-map.get(prefix[i]),max);
                }else{map.put(prefix[i], i);
                }
            }
            return max;
        }

工夫复杂度 O(n)