跳到主要内容

数组子数组

一、连续数组​

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

1.1 前缀和 + 哈希表​

思路: 0 和 1 的数量相同等价于 1 的数量减去 0 的数量等于 0，我们可以将数组中的 0 视作 −1，则原问题转换成求最长的连续子数组，其元素和为 0。设数组 nums 的长度为 n，将数组 nums 进行转换得到长度相等的新数组 newNums: 对于 0≤i<n0，当 nums[i]=1 时 newNums[i]=1，当 nums[i]=0 时 newNums[i]=−1。为了快速计算 newNums 的子数组的元素和，需要首先计算 newNums 的前缀和。用 prefixSums[i] 表示 newNums 从下标 0 到下标 i 的前缀和，则 newNums 从下标 j+1 到下标 k（其中 j<k）的子数组的元素和为 prefixSums[k]−prefixSums[j]，该子数组的长度为 k−j。当 prefixSums[k]−prefixSums[j]=0 时，即得到 newNums 的一个长度为 k−j 的子数组元素和为 0，对应 nums 的一个长度为 k−j 的子数组中有相同数量的 0 和 1。

实现: 实现方面，不需要创建数组 newNums 和 prefixSums，只需要维护一个变量 counter 存储 newNums 的前缀和即可。具体做法是，遍历数组 nums，当遇到元素 1 时将 counter 的值加 1，当遇到元素 0 时将 counter 的值减 1，遍历过程中使用哈希表存储每个前缀和第一次出现的下标。

  • 如果 counter 的值在哈希表中已经存在，则取出 counter 在哈希表中对应的下标 prevIndex，nums 从下标 prevIndex+1 到下标 i 的子数组中有相同数量的 0 和 1，该子数组的长度为 i−prevIndex，使用该子数组的长度更新最长连续子数组的长度

  • 如果 counter 的值在哈希表中不存在，则将当前余数和当前下标 i 的键值对存入哈希表中

由于哈希表存储的是 counter 的每个取值第一次出现的下标，因此当遇到重复的前缀和时，根据当前下标和哈希表中存储的下标计算得到的子数组长度是以当前下标结尾的子数组中满足有相同数量的 0 和 1 的最长子数组的长度。遍历结束时，即可得到 nums 中的有相同数量的 0 和 1 的最长子数组的长度。

function findMaxLength(nums){
    let maxLength = 0;
    const map = new Map();
    let counter = 0;
    map.set(counter, -1);
    const n = nums.length;
    for(let i=0; i<n; i++){
        const num = nums[i];
        if(num === 1){
            counter++;
        }else{
            counter--;
        }
        if(map.has(counter)){
            const prevIndex = map.get(counter);
            maxLength = Math.max(maxLength, i - prevIndex);
        }else{
            map.set(counter, i);
        }
    }
    return maxLength;
}

二、和为 K 的子数组​

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

示例1:

输入：nums = [1,1,1], k = 2
输出：2

示例2:

输入：nums = [1,2,3], k = 3
输出：2

2.1 前缀和和哈希表​

思路

  1. 通过 prev 记录 [0,i] 区间的前缀和, 以 prev 为键, 以出现次数为值, 记录在Map中

  2. [0,i] 区间的前缀和与[0,xxx]区间的前缀和关系为: [0,i] 前缀和 - k = [0,xxx] 区间前缀和 , 所以, 计算 k 出现次数, 也就是计算 [0,xxx] 区间前缀和 出现次数, 也就是 [0,i] 前缀和 - k 出现次数, 也就是 prev - k 在 Map 中的次数

实现

function subarraySum(nums, k) {
  const map = new Map();
  map.set(0, 1);
  let count = 0;
  let prev = 0;
  for (const num of nums) {
    prev += num;
    if (map.has(prev - k)) {
      count += map.get(prev - k);
    }
    if (map.has(prev)) {
      map.set(prev, map.get(prev) + 1);
    } else {
      map.set(prev, 1);
    }
  }
  return count;
}

  • 时间复杂度: O(n)

  • 空间复杂度: O(n)

三、连续子数组的最大和​

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

3.1 动态规划​

思路: 用 f(i) 代表以第 i 个数结尾的连续子数组的最大和

  1. 动态转移方程为: f(i)=max{f(i−1)+nums[i],nums[i]}

  2. 初始值: dp = nums[0]

  3. 利用滚动数组节省空间

实现

function maxSubArray(nums) {
  let pre = 0;
  let dp = nums[0];
  for (let num of nums) {
    pre = Math.max(pre + num, num);
    dp = Math.max(dp, pre);
  }
  return dp;
}