leetcode 525. 连续数组(优质解法)

2023-12-21 12:19:47

代码:

class Solution {
    public int findMaxLength(int[] nums) {
        HashMap<Integer,Integer> hashMap=new HashMap<>();
        hashMap.put(0,-1);

        int max_length=0;
        int last=0; //上一个下标的前缀和
        int now=0;  //当前下标的前缀和
        for(int i=0;i<nums.length;i++){
            int num=nums[i]==0?-1:1;    //获取当前的数据,0要视为-1
            now=last+num;
            int j=hashMap.getOrDefault(now,-2); 
            if(j!=-2){
                max_length=Math.max(max_length,i-j);
            }else{
                hashMap.put(now,i);
            }
            last=now;
        }

        return max_length;
    }
}

题解:

? ? ? ? 本题我们要找到有相同数量 0 和 1 的最长子数组,要是直接按原题这种数据来解题的话是比较困难的,对于该题我们应该换一个思路,把 0 视为 -1,那么我们要找的就是有相同数量 -1?和 1 的最长子数组,那么子数组的和就为 0 , 我们要找的就是和为 0 的最长子数组

? ? ? ? 对于找子数组的题通常使用滑动窗口和前缀和,一般数组中具有单调性就使用滑动窗口,涉及到子数组的和就使用前缀和,很显然本题可以通过前缀和来解决

? ? ? ? 为了方便分析,我画了如下的图:

? ? ? ? sum 是前缀和数组,记录对应下标的前缀和。要寻找以 i 为尾,符合条件的子数组,加上在 0 ~ i -1 区间找到了下标 j ,j +1 - i 的子数组是符合条件的,那么 x = 0 ,并且 x= sum[ i ] - sum[ j ] ,推得:sum[ i ] = sum[ j ] ,所以要想获得 j 下标,就要判断 i 下标之前有多少下标的前缀和等于 sum[ i ]?

? ? ? ? 可以将 i 下标之前下标的前缀和存放到哈希表中,由于本题要获取的是最长子数组,所以在哈希表中以下标的前缀和为 key ,下标为 value,可以通过 j 下标与 i 下标的距离得到符合条件的子数组的长度

? ? ? ? 将前缀和以及下标存储到哈希表中时可能会出现冲突,我们要考虑如何解决,当不同的下标对应相同的前缀和时,应该存储较小的下标,因为较小的下标离 i 下标较远,得到的子数组长度更长

? ? ? ? 在使用 前缀和+哈希表 的解题方法时,哈希表一般都需要先填入一个初始数据,我们通过示例 1 来进行分析,nums=[ 0,1 ]

? ? ? ? i 下标一开始指向 0 ,当数据是 0 时视为 -1,所以此时的前缀和为 -1,要在哈希表中找的 key 值就是 -1,哈希表中没有,于是准备遍历下一个数据,在遍历之前先将当前下标的前缀和以及下标填入哈希表,

0? ? ? ? 1? ? ? ? hash

i????????????????????????

? ? ? ? i 此时指向 1 ,前缀和为 0 ,所以在哈希表中找的 key 值就是 0,哈希表中没有,但是我们知道以当前位置为末尾是有符合条件的子数组的,就是 0,1,通过上面画的图知道,子数组的长度为 i - j ,此时符合条件的子数组长度为 2 ,i 为 1,所以 j 为 -1,所以我们要在哈希表在填入的初始数据为 (0,-1)

0? ? ? ? 1? ? ? ? hash

? ? ? ? ? ?i? ? ? ? ? ? -1,0

? ? ? ? 上述便是本题的核心思想

文章来源:https://blog.csdn.net/q322359/article/details/135124347
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。