一维数组前缀和

前缀和数组

  1. int n = nums.length;
  2. // 前缀和数组
  3. int[] preSum = new int[n + 1];
  4. preSum[0] = 0;
  5. for (int i = 0; i < n; i++)
  6.     preSum[i + 1] = preSum[i] + nums[i];

525. 连续数组

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

https://leetcode-cn.com/problems/contiguous-array/solution/525lian-xu-shu-zu-qian-zhui-he-hashbiao-riqe2/
图片.png

参考代码

  1. class Solution:
  2.     def findMaxLength(self, nums):
  3.         d = {0: -1}
  4.         ret = pre_sum = 0
  5.         for i, num in enumerate(nums):
  6.             pre_sum += 1 if num == 1 else -1
  7.             pre_index = d.get(pre_sum, i)
  8.             if pre_index == i:
  9.                 d[pre_sum] = i
  10.             else:
  11.                 ret = max(ret, i - pre_index)
  12.         return ret
  14. 作者：qingfengpython
  15. 链接：https://leetcode-cn.com/problems/contiguous-array/solution/525lian-xu-shu-zu-qian-zhui-he-hashbiao-riqe2/
  16. 来源：力扣（LeetCode）
  17. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  1. class Solution:
  2.     def findMaxLength(self, nums: List[int]) -> int:
  3.         n = len(nums)
  4.         # 将 0全部看成 - 1
  5.         for i in range(n):
  6.             if nums[i] == 0:
  7.                 nums[i] = - 1
  8.         # 求出前缀和
  9.         '''
  10.         对应构造数组
  11.            0  0   1  0  0  0  1  1
  12.         0 -1 -2  -1 -2 -3 -4 -3  -2
  13.         '''
  14.         presum = [0 for _ in range(n + 1)]
  15.         for i in range(1, n + 1):
  16.             presum[i] = presum[i - 1] + nums[i - 1]
  17.         # 求出前缀和以及第一个出现的位置
  18.         presum_first = {}
  19.         for idx, pre in enumerate(presum):
  20.             if pre not in presum_first:
  21.                 presum_first[pre] = idx
  22.         # 得到结果 cur_res = 当前前缀和下标 - 第一次前缀和下标
  23.         res = 0
  24.         for i in range(1, len(presum)):
  25.             var1 = presum[i] # 当前的前缀和的值
  26.             var2 = presum_first[var1] # 当前前缀和最早的下标
  27.             res = max(res, i - var2) # 求出最大长度
  28.         return res

图片.png、

https://leetcode-cn.com/problems/contiguous-array/solution/jin-dao-san-chong-fang-fa-mei-ju-qian-zh-on9x/

class Solution {
    public int findMaxLength(int[] nums) {
        int result = 0;
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        int prefix = 0; // 当前子数组的前缀和
        hash.put(0, -1); // 空前缀为0，下标为 −1
        int n = nums.length;
        for (int right = 0; right < n; right++) {
            if (nums[right] == 0) { // 数组中的 0 变成 −1
                nums[right] = -1;
            }
            //前缀和，nums[0]...nums[right]之和
            prefix = prefix + nums[right];

            // 哈希表存储每个前缀和第一次出现时末尾元素的下标
            // 其中putIfAbsent方法只有当key不存在哈希表中时，才会存储value
            hash.putIfAbsent(prefix, right);

            // right - hash.get(prefix)为符合新问题2中的条件的子数组的长度
            result = Math.max(result, right - hash.get(prefix));
        }
        return result;
    }
}


作者：glodknife
链接：https://leetcode-cn.com/problems/contiguous-array/solution/jin-dao-san-chong-fang-fa-mei-ju-qian-zh-on9x/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

560. 和为 K 的子数组

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

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

提示：

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

通过次数191,993
提交次数428,385

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        hashmap = defaultdict(int)
        hashmap[0] = 1
        ans = 0
        pre_sum = 0
        for i, n in enumerate(nums):
            pre_sum += n 
            remain = pre_sum - k 
            if remain in hashmap:
                ans += hashmap[remain]
            hashmap[pre_sum] += 1 
        return ans

2090. 半径为 k 的子数组平均值

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。
半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。
构建并返回一个长度为 n 的数组avgs，其中avgs[i]是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。
x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。

  • 例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

示例 1：
前缀和 & 差分 - 图3
输入：nums = [7,4,3,9,1,8,5,2,6], k = 3 输出：[-1,-1,-1,5,4,4,-1,-1,-1] 解释： - avg[0]、avg[1] 和 avg[2] 是 -1 ，因为在这几个下标前的元素数量都不足 k 个。 - 中心为下标 3 且半径为 3 的子数组的元素总和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。 使用截断式 整数除法，avg[3] = 37 / 7 = 5 。 - 中心为下标 4 的子数组，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。 - 中心为下标 5 的子数组，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。 - avg[6]、avg[7] 和 avg[8] 是 -1 ，因为在这几个下标后的元素数量都不足 k 个。
示例 2：
输入：nums = [100000], k = 0 输出：[100000] 解释： - 中心为下标 0 且半径 0 的子数组的元素总和是：100000 。 avg[0] = 100000 / 1 = 100000 。
示例 3：
输入：nums = [8], k = 100000 输出：[-1] 解释： - avg[0] 是 -1 ，因为在下标 0 前后的元素数量均不足 k 。

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 0 <= nums[i], k <= 105

通过次数5,877
提交次数16,600

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        pre_sum = [0] * (n + 1)
        for i in range(n):
            pre_sum[i + 1] = pre_sum[i] + nums[i]
        ans = [-1] * n
        for i in range(k, n - k):
            temp = pre_sum[i + k + 1] - pre_sum[i - k]
            ans[i] = temp // (2 * k + 1)
        return ans

二维数组前缀和

https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/ru-he-qiu-er-wei-de-qian-zhui-he-yi-ji-y-6c21/ 

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.matrix = matrix
        m = len(matrix)
        n = len(matrix[0])
        self.pre_sum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                self.pre_sum[i + 1][j + 1] = self.pre_sum[i][j+1] +self.pre_sum[i+1][j] - self.pre_sum[i][j] + self.matrix[i ][j]

                def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.pre_sum[row2 + 1][col2 + 1] - self.pre_sum[row2 + 1][col1] - self.pre_sum[row1][col2 + 1] + self.pre_sum[row1][col1]

差分

1109. 航班预订统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 输出：[10,55,45,25,25] 解释： 航班编号 1 2 3 4 5 预订记录 1 ： 10 10 预订记录 2 ： 20 20 预订记录 3 ： 25 25 25 25 总座位数： 10 55 45 25 25 因此，answer = [10,55,45,25,25]
示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2 输出：[10,25] 解释： 航班编号 1 2 预订记录 1 ： 10 10 预订记录 2 ： 15 总座位数： 10 25 因此，answer = [10,25]

提示：

  • 1 <= n <= 2 * 104
  • 1 <= bookings.length <= 2 * 104
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 104
class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * n
        for s, e, z in bookings:
            diff[s - 1] += z
            if e < n:
                diff[e] -= z
        res = [0] * n
        res[0] = diff[0]
        for i in range(1, len(diff)):
            res[i] = res[i - 1] + diff[i]
        return res