「优选算法刷题」：连续数组

一、题目

给定一个二进制数组 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

  二、思路解析

  看到这道题，我的第一想法是遍历数组，然后用哈希表记录每次遍历的结果，与子数组长度最长的一次判断，然后更新结果。

  然后我在思考如何优化的时候，看到一位大神的奇特思路：

  • 本题让我们找出⼀段连续的区间， 0 和 1 出现的次数相同。

  • 如果将 0 记为 -1 ， 1 记为 1 ，问题就变成了找出⼀段区间，这段区间的和等于 0 。

  而哈希表 hash ，中的键值对分别表示：

  • 键（Key）：键表示数组中 0 和 1 的数量之差，也就是变量 sum 的值。

  • 值（Value）：值表示对应键（即差值 sum）最后一次出现的索引位置。

    三、完整代码

    class Solution {
        public int findMaxLength(int[] nums) {
            int ret = 0;
            int sum = 0;
            Map hash = new HashMap();
            hash.put(0 , -1);
            for(int i = 0; i < nums.length ; i++){
                sum += (nums[i] == 0 ? -1 : 1);
                if(hash.containsKey(sum)){
                    ret = Math.max(ret , i - hash.get(sum));
                }else{
                    hash.put(sum , i);
                }
            }
                return ret;
        }
    }

    以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！