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)