前缀和

【西法带你学算法】一次搞定前缀和 | lucifer的网络博客

1109. 航班预订统计 - 力扣（LeetCode）

暴力是绝对不行的, 这题应该用 差分法,应为差分法的特征太过明显, 值得为之单独开个专题!

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        res = [0] * (n + 2)
        for i in bookings:
            res[i[0]] += i[2]
            res[i[1] + 1] -= i[2]
        for i in range(len(res) - 1):
            res[i + 1] = res[i] + res[i + 1]
        return res[1:-1]

这题值得背诵>>>

724. 寻找数组的中心下标 - 力扣（LeetCode）

必须熟练掌握前缀和

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        presum = [0] * len(nums)
        for i in range(len(nums)):
            presum[i] = nums[0] if i == 0 else presum[i - 1] + nums[i]
        presum.insert(0, 0)
        presum.append(presum[-1])
        for i in range(1, len(presum) - 1):
            if presum[i - 1] == presum[-1] - presum[i]:
                return i - 1
        return -1

560. 和为 K 的子数组 - 力扣（LeetCode）

这道题前缀和很好想, 但难得是 哈希表, 这题一定要熟练掌握!

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        presum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            presum[i + 1] = presum[i] + nums[i]
        l = 0
        count = 0
        dir = {}
        for i in range(len(presum)):
            if presum[i] - k in dir:
                count += dir[presum[i] - k]
            if presum[i] in dir:
                dir[presum[i]] += 1
            else:
                dir[presum[i]] = 1
        return count

238. 除自身以外数组的乘积 - 力扣（LeetCode）

题目描述：有个数组 nums，需要返回一个 answer 数组， answer[i] 的值是 nums 中除 nums[i] 外其他数的乘积。

• 方法一：维护两个乘积数组，分别记录左起的乘积和右起的乘积。
• 方法二：
• 方法三：
  注意：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left_presum = [0] * len(nums)
        right_presum = [0] * len(nums)
        for i in range(len(nums)):
            if i == 0:
                left_presum[i] = nums[0]
            else:
                left_presum[i] = nums[i] * left_presum[i - 1]
        for j in range(-1, -len(nums) - 1, -1):
            if j == -1:
                right_presum[j] = nums[j]
            else:
                right_presum[j] = nums[j] * right_presum[j + 1]
        return_list = [0] * len(nums)
        for i in range(len(return_list)):
            return_list[i] = (left_presum[i - 1] if i - 1 >= 0 else 1) * (
                right_presum[i + 1] if i + 1 < len(nums) else 1
            )
        return return_list

function productExceptSelf(nums: number[]): number[] {
  let leftMulti = Array.from({ length: nums.length + 1 }, () => 1);
  let rightMulti = Array.from({ length: nums.length + 1 }, () => 1);
  for (let i = 0; i < nums.length; i++) {
    leftMulti[i + 1] = leftMulti[i] * nums[i];
    rightMulti[nums.length - i - 1] =
      rightMulti[nums.length - i] * nums[nums.length - 1 - i];
  }
  let returnArr = Array.from({ length: nums.length }, () => 0);
  for (let i = 0; i < returnArr.length; i++) {
    returnArr[i] = leftMulti[i] * rightMulti[i + 1];
  }
  return returnArr;
}

304. 二维区域和检索 - 矩阵不可变 - 力扣（LeetCode）

二维前缀和的核心关键是要先扩容!!!

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.matrix =[[0]*(len(matrix[0])+1) for _ in range(len(matrix)+1)]
        for i in range(len(matrix)):
            matrix[i].insert(0,0)
        matrix.insert(0,[0]*len(matrix[0]))
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                    self.matrix[i][j] = self.matrix[i][j-1]+matrix[i][j]+self.matrix[i-1][j]-self.matrix[i-1][j-1]
        print(self.matrix)
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        sum = self.matrix[row2+1][col2+1]-self.matrix[row2+1][col1]-self.matrix[row1][col2+1]+self.matrix[row1][col1]
        return sum

497. 非重叠矩形中的随机点 - 力扣（LeetCode）

一道结合了 bisect 和 presum 思想的题,值得多看多思考

import random
import bisect
class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        square = [(item[2]-item[0]+1)*(item[3]-item[1]+1) for item in rects]
        self.presum = [0]*(len(rects)+1)
        for i in range(1,len(self.presum)):
            self.presum[i] = self.presum[i-1]+square[i-1]
    def pick(self) -> List[int]:
        rand_len = self.presum[-1]*random.random()
        index = bisect.bisect_left(self.presum,rand_len,0,len(self.presum))
        number_rect = index-1
        return [random.randint(self.rects[number_rect][0],self.rects[number_rect][2]),random.randint(self.rects[number_rect][1],self.rects[number_rect][3])]

525. 连续数组 - 力扣（LeetCode）

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        count = 0
        max_length = 0
        table = {0: -1}  
        for i, num in enumerate(nums):
            if num == 0:
                count -= 1  
            else:
                count += 1
            if count in table:
                max_length = max(max_length, i - table[count])
            else:
                table[count] = i
        return max_length

974. 和可被 K 整除的子数组 - 力扣（LeetCode）

这题需要意识到 -5%5 也是可以的,所以可以只看余数,同余即可

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        def return_all_res(num,k):
            arr = []
            for i in range(num//k+1):
                arr.append(num%k+k*i)
            return arr
        dir = {}
        presum = [0]*(len(nums)+1)
        for i in range(1,len(presum)):
            presum[i] = nums[i-1]+presum[i-1]
        presum.sort()
        count = 0
        print(presum)
        for i in range(len(presum)):
            j = presum[i]%k
            if j in dir:
                count+=dir[j]
                dir[j]+=1
            else:
                dir[j]=1
        return count