leetcode
leetcode 2901 ~ 2950
连续数组

连续数组

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 107 ms, 内存: 23.7 MB


/*
思路:
Java Stream 不能直接处理这个问题,因为我们需要跟踪累积和的下标。因此,我们在这里不使用 Stream,而是尽量简洁地使用常规方法。
步骤与上面相同。
*/
import java.util.HashMap;
import java.util.stream.IntStream;

public class Solution {
    public int findMaxLength(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1); // 初始化累积和为0的位置为-1
        int[] count = {0};
        int[] maxLength = {0};
        IntStream.range(0, nums.length).forEach(i -> {
            count[0] += (nums[i] == 1) ? 1 : -1;
            if (map.containsKey(count[0])) {
                maxLength[0] = Math.max(maxLength[0], i - map.get(count[0]));
            } else {
                map.put(count[0], i);
            }
        });
        return maxLength[0];
    }
}

解释

方法:

该题解采用了哈希表记录前缀和的方法。定义cur为当前前缀和,遍历数组nums时,遇到1则cur加1,遇到0则cur减1。用一个字典dic记录cur第一次出现的位置和最后一次出现的位置。最后,遍历dic中的所有值,计算最大的位置差值,即为含有相同数量的0和1的最长连续子数组的长度。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在遍历数组时选择用前缀和的方式表示0和1的数量关系?
使用前缀和来表示0和1的数量关系是一种有效的方法来检测子数组中0和1的数量是否相等。在这种方法中,每遇到1,前缀和增加1;每遇到0,前缀和减少1。这样,如果在两个不同位置的前缀和相同,意味着这两个位置之间的子数组中0和1的数量正好抵消,即数量相等。这种方法利用了数学中的差分原理,是解决这类问题的一种高效技术。
🦆
字典中存储前缀和的第一次和最后一次出现的位置,这种方法能够确保计算的子数组确实是0和1数量相等吗?
是的,这种方法确保了计算的子数组中0和1的数量相等。当我们记录下一个前缀和首次和最后一次出现的位置时,其实是在找到所有相同前缀和的区间。若两个位置的前缀和相同,那么这两个位置之间的区间(不包括第一个位置)的前缀和的变化量为零,即这个区间内0和1的数量相等。因此,通过计算这两个位置的差值,我们可以得到一个0和1数量相等的子数组的长度。
🦆
代码中对于前缀和为0的特殊处理`res = max(res, dic[0][1] + 1)`的逻辑是什么?为什么要加1?
前缀和为0的特殊处理是因为当前缀和为0时,它表示从数组开始到当前位置的全部元素构成的子数组0和1的数量完全相等。dic[0][1]是前缀和为0最后一次出现的位置,即从索引0到dic[0][1]的子数组是平衡的。因为数组索引从0开始计数,所以要加1来正确计算这个子数组的长度(包括起始点)。例如,如果前缀和为0最后一次出现在索引5,那么从索引0到索引5的子数组长度为6,这就是为什么要加1的原因。

相关问题