当前位置：首页 > article >正文

【LeetCode每日一题】525连续数组 303区域和检索（前缀和的基本概念和3个简单案例）

article 2024/11/15 19:01:49

前缀和

在这里插入图片描述

// 构造prefix
let prefix = [0]
arr.forEach(num => {
    prefix.push(prefix.at(-1) + num);
})

如果想要计算某个区间 i 到 j 这个子数组的和时，可以根据 prefix[j+1] - prefix[i] 获得。

例题1：303.区域和检索 - 数组不可变

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    this.sum = new Array(nums.length+1).fill(0);
    for(let i =0;i<n;i++){
        this.sum[i+1] = this.sum[i]+nums[i]
    }
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    return this.sum[right+1 ]-this.sum[left];
};

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(left,right)
 */

例题2

数组water表示一排瓶子的水位高度。小明往这些瓶子内浇水，1次操作可以使1个瓶子的水位增加1。给定一个整数cnt，表示小明想通过浇水获得cnt个水位高度一致的瓶子。求最少需要浇水多少次？

比如：[1,2,3,4,100] ,cnt = 4，想要获得4个，最少需要浇水
（4-1） + （4-2）+（4-3）+（4-4）
⇒ 4 * 4 - （1+2+3+4）
⇒ 4* cnt - cnt个元素的区域和。

计算操作次数的公式为：water[i] * cnt - (preSum[i + 1] - preSum[i - cnt + 1])。
这个公式表示将当前位置到第cnt个瓶子的水位高度都调整为当前位置的水位高度所需的总操作次数。

下面是修改后的代码实现：

const MinOperations = (water, cnt) => {
  water.sort((a, b) => b - a); // 按照从大到小排序
  let preSum = [0];
  water.forEach((element) => {
    preSum.push(preSum[preSum.length - 1] + element);
  });

  let res = Infinity;
  for (let i = cnt - 1; i < water.length; i++) {
    let temp = water[i] * cnt - (preSum[i + 1] - preSum[i - cnt + 1]);
    if (temp < res) res = temp;
    if (res === 0) break; // 如果res的值已经为0，表示不需要再进行更多操作，可以跳出循环
  }
  return res;
};

console.log(MinOperations([7, 1, 9, 10], 3));
console.log(MinOperations([5, 3, 5, 10], 2));

在给定的示例中，第一个输入数组为[7, 1, 9, 10]，表示瓶子的水位高度，cnt为3。运行代码后，输出为2，表示最少需要浇水2次才能使3个瓶子的水位高度一致。第二个输入数组为[5, 3, 5, 10]，cnt为2。运行代码后，输出为3，表示最少需要浇水3次才能使2个瓶子的水位高度一致。

例题3：525. 连续数组

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

妈的连题目都没有读懂！本来看成是找到两个连续子数组，两个连续子数组的 0 1 个数分别相同，我说怎么看着如此复杂。

题目转换：

找到一个连续子数组，其中0和1 的数量是一致的，求最大的连续子数组的长度。

解题过程

暴力：

遍历所有连续子数组的0和1 的个数，如果相同，则维护这个连续子数组的最大长度。

巧妙的转换：

相同数量的0和1 ⇒ 将 0 → -1 ⇒ 连续子数组和为 0

如果想要求子数组的元素和 ⇒ 计算数组的前缀和。

prefixSum[i] ： [0…i] 的前缀和，元素的累加。

[i…k] 的元素累加和 = prefixSum[k]-prefixSum[i-1]

所以：相同数量的0和1 ⇒ 将 0 → -1 ⇒ 连续子数组和为 0 ⇒ prefixSum[k]-prefixSum[i] = 0 长度为 i- k ⇒ 当出现前缀和相同时维护一个最大的长度。

思路1：（x）

维护一个prefixSum表。遍历nums
用两个for循环，遍历所有子数组。

思路2：

用一个map记录前缀和和第一次出现的位置。key⇒value 的形式。
map.has 意味着出现了前缀和一致的情况，则维护最大长度。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function(nums) {
  let max = 0;
	// 如果连续子数组索引从0开始，则是priefix-prefix[-1],因此要提前保存-1，但是很难想到。
  const map = new Map();
	map.set(0,-1)

  let sum= 0;

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 0) {
      sum--; // 遇到0 则-1，相当于把0元素简化为-1
    } else {
      sum++;
    }

    if (map.has(sum)) {
    // 出现了相同的前缀和，相减=0，说明这个区域和为0，说明0和1的个数相同
      max = Math.max(max, i - map.get(sum));// 不用更新sum的索引，因为要求的是最大的
    } else {
      map.set(sum, i);
    }
  }

  return max;
};

思路3：

最长的连续子数组是以index = 0 为开头的特殊情况，要么使用思路二，在map里添加 index = -1 的情况。

要么使用思路三：sum = 0 的情况，sum是从index = 0 开始算的，相当于算的就是每个以index = 0 为开头的连续子数组的和。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function(nums) {
  let max = 0;
  const map = new Map();
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 0) {
      sum --;
    } else {
      sum ++;
    }
		if(sum === 0){max = Math.max(max,i+1)}
    else if (map.has(sum)) {
      max = Math.max(max, i - map.get(sum));
    } else {
      map.set(sum , i);
    }
  }

  return max;
};