前缀和

一维前缀和

模版题

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var reader = bufio.NewReader(os.Stdin)
    var x = readArray(reader)
    //var n, m = x[0], x[1]
    var nums = readArray(reader)
    var sums = make([]int, x[0]+1)
    for i := 0; i < x[0]; i++ {
        sums[i+1] = sums[i] + nums[i]
    }

    var cnt int
    var xx []int
    for cnt < x[1] {
        xx = readArray(reader)
        // 请注意题目下标是从1开始的
        fmt.Println(sums[xx[1]] - sums[xx[0]-1])
        cnt++
    }
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var num, _ = strconv.Atoi(readLine(reader))
    return num
}

func readArray(reader *bufio.Reader) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, " ")
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

func nums2string(x []int, sep string) string {
    var b strings.Builder
    for i := 0; i < len(x); i++ {
        b.WriteString(strconv.Itoa(x[i]))
        b.WriteString(sep)
    }
    return b.String()
}

/*
输入一个长度为n的整数序列。

接下来再输入m个询问，每个询问输入一对l, r。

对于每个询问，输出原序列中从第l个数到第r个数的和。

输入格式
第一行包含两个整数n和m。

第二行包含n个整数，表示整数数列。

接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。

输出格式
共m行，每行输出一个询问的结果。

数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000
输入样例：
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例：
3
6
10
*/

查找数组和

# 查找数组和
def search_sum(nums, lst):
    sums = [0] * (len(nums) + 1)
    # 查找前缀和
    for i in range(len(nums)):
        sums[i + 1] = sums[i] + nums[i]

    # 查找前缀和
    for left, right in lst:
        print(sums[right + 1] - sums[left])

if __name__ == '__main__':
    search_sum([1, 2, 3, 4, 5, 6], [(1, 3)])

和为K的子数组

Python3

# [和为K的子数组](https://leetcode-cn.com/problems/subarray-sum-equals-k/)
# 数据增强后O(N*N)已经过不了，Python版本
from typing import List
from collections import defaultdict


class Solution:
    # def subarraySum(self, nums: List[int], k: int) -> int:
    #     sums = [0] * (len(nums) + 1)
    #     # 求前缀和
    #     for i in range(len(nums)):
    #         sums[i + 1] = sums[i] + nums[i]
    #
    #     cnt = 0
    #     # 查找前缀和
    #     for i in range(len(sums) - 1):
    #         for j in range(i + 1, len(sums)):
    #             if sums[j] - sums[i] == k:
    #                 cnt += 1
    #     return cnt

    # 使用Map进行优化（只适用于统计次数而不关心具体的解） 时间复杂度O(N)
    def subarraySum(self, nums: List[int], k: int) -> int:
        dd = defaultdict(int)
        sums = 0
        dd[sums] = 1
        cnt = 0
        for num in nums:
            sums += num
            cnt += dd[sums - k]
            dd[sums] += 1
        return cnt

二维前缀和

S[i,j]即为左图红框中所有数的的和为：S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j] (x1,y1),(x2,y2)这一子矩阵中的所有数之和为：S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1]

模版题

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var reader = bufio.NewReader(os.Stdin)
    var x = readArray(reader)
    var sums = make([][]int, x[0]+1)

    var nums = make([][]int, x[0])
    for i := 0; i < x[0]; i++ {
        nums[i] = readArray(reader)
    }

    for i := 0; i < x[0]+1; i++ {
        sums[i] = make([]int, x[1]+1)
    }
    for i := 0; i < x[0]; i++ {
        for j := 0; j < x[1]; j++ {
            sums[i+1][j+1] = sums[i+1][j] + sums[i][j+1] + nums[i][j] - sums[i][j]
        }
    }

    var cnt int
    var xx []int
    for cnt < x[2] {
        xx = readArray(reader)
        p(sums, xx)
        cnt++
    }
}

func p(sums [][]int, xx []int) {
    var a, b, c, d = xx[0], xx[1], xx[2], xx[3]
    // 建议画个图梳理关系 // https://www.acwing.com/solution/content/3797/
    fmt.Println(sums[c][d] + sums[a-1][b-1] - sums[a-1][d] - sums[c][b-1])
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var num, _ = strconv.Atoi(readLine(reader))
    return num
}

func readArray(reader *bufio.Reader) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, " ")
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

func nums2string(x []int, sep string) string {
    var b strings.Builder
    for i := 0; i < len(x); i++ {
        b.WriteString(strconv.Itoa(x[i]))
        b.WriteString(sep)
    }
    return b.String()
}

/*
输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式
第一行包含三个整数n，m，q。

接下来n行，每行包含m个整数，表示整数矩阵。

接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。

输出格式
共q行，每行输出一个询问的结果。

数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n ,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21
*/

统计全为1的正方形子矩阵

Python3（超时）

# [统计全为1的正方形子矩阵](https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/)
from typing import List


class Solution:
    # 超时O(N^3)
    def countSquares(self, matrix: List[List[int]]) -> int:
        x = len(matrix)
        if x == 0:
            return 0
        y = len(matrix[0])
        if y == 0:
            return 0

        sums = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
        # 构造前缀和
        for i in range(x):
            for j in range(y):
                sums[i + 1][j + 1] = sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + matrix[i][j]

        cnt = 0
        # 查找前缀和
        # 扫描所有正方形
        # 边长
        for length in range(1, min(x, y) + 1):
            for i in range(0, x - length + 1):
                for j in range(0, y - length + 1):
                    cnt += sums[i + length][j + length] - sums[i][j + length] - sums[i + length][j] + sums[i][
                        j] == length * length

        return cnt

        # 这道题需要使用DP进行解答，这里只是一个使用二维前缀和解答的例子
        # 从时间复杂度看（数据范围是0--300）, 对于O(N^3)则数据量级达27000000，Python版本可能会超时，使用go不会
        # go版本见同目录下的lc1277

Golang

package main

func countSquares(matrix [][]int) int {

    var (
        x int
        y int
        sums [][]int
        cnt int
    )
    x = len(matrix)
    if x == 0 {
        return 0
    }
    y = len(matrix[0])
    if y == 0 {
        return 0
    }
    // 初始化
    sums = make([][]int, x+1, x+1)
    for i := 0; i< x+1; i++ {
        sums[i] = make([]int, y+1, y+1)
    }
    // 填充前缀和
    for i :=0; i< x; i++ {
        for j:=0; j < y; j++ {
            sums[i+1][j+1] = sums[i+1][j] + sums[i][j+1] - sums[i][j] + matrix[i][j]
        }
    }

    // 查找前缀和
    // 扫描所有正方形
    // 边长
    var b = x
    if y < x {
        b = y
    }
    for length:=1 ;length< b+1; length ++ {
        for i:= 0; i<x-length+1; i++ {
            for j:=0; j < y-length+1; j++ {
                if sums[i + length][j + length] - sums[i][j + length] - sums[i + length][j] + sums[i][j] == length * length {
                    cnt++
                }
            }
        }
    }

    return cnt
}