2.3 累加数组数字求子数组之和

Kesa...大约 6 分钟

使用双指针求子数组之和的前提是元素均为正整数, 否则添加或删除元素并不能保证和的减小或增大.

前缀和:

对于数组 [ $a_0, a_1, ..., a_{n-1}$ ], 从第一个到第 k 个的元素之和记为 $S_{k} = a_0 + a_1 + ... + a_k$ .

那么子数组 [ $a_i, a_{i+1}, ..., a_j$ ] 的和可以表示为 $S_j - S_{i-1}$ = $(a_0 + ... + a_{i-1} + a_i + ... + a_j) - (a_0 + ... + a_{i-1}) = a_i + ... + a_j$

2.3.1 问题10: 和为 k 的子数组

输入: 整数数组和整数k

输出: 子数组之和为k的子数组个数

例: [1 1 1]和2, [1 1] [1 1] 满足条件, 输出2

2.3.1.1 分析&题解

由于数组元素不一定是正整数, 那么不能使用双指针法.

暴力解法 TC: O( $n^3$ )

计算每个子数组的和, 寻找子数组时间为 O( $n^2$ ) 为计算子数组之和时间O(n), 总体时间为 O( $n^3$ )

func subarraySumBruteForce(nums []int, k int) int {
	count := 0
	for i := 0; i < len(nums); i++ {
		for j := i; j < len(nums); j++ {
			sum := 0
			for k := i; k <= j; k++ {
				sum += nums[k]
			}
			if sum == k {
				count++
			}
		}
	}

	return count
}

暴力解法 - 优化 TC: O( $n^2$ )

计算数组元素和时, 将前一个子数组元素和 $S_i$ 记录下来, 那么下一个数组元素和即为 $S_{i+1} = S_i + a_{i+1}$

时间复杂度优化为 O( $n^2$ )

func subarraySumBruteForceOptimized(nums []int, k int) int {
	count := 0
	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum += nums[j]
			if sum == k {
				count++
			}
		}
	}

	return count
}

HashTable TC: O(n) SC: O(n)

每次将前 i 个元素之和 $S_i$ 记录下来, 那么对于子数组 $[a_{j+1}, ..., a_i](j > i)$ 若和 $S=k$ , 则有 $S = S_i - S_j = k$ , 则 $S_j = S_i - k$

那么问题就转化为寻找满足条件的 j 的个数:

构建哈希表, Key: 前 i 个元素和, Val: 和出现的次数
遍历数组:
1. 计算前 i 个元素和 S
2. 统计 Key 为 S-k 的次数,
3. 存入当前结果S .
返回结果

func subarraySumHashTable(nums []int, k int) int {
	m := make(map[int]int, len(nums))
	count := 0
	// 当前子数组满足条件,故次数为1
	m[0] = 1
	sum := 0
	for _, v := range nums {
		sum += v
		if val, ok := m[sum-k]; ok {
			count += val
		}
		m[sum] += 1

	}

	return count
}

注意: m[0] 表示当前子数组就是满足条件的, 故出现的次数 m[0] = 1

2.3.2 问题11: 0和1个数相同的子数组

输入: 只包含0和1的数组

输出: 0和1个数相同的最长连续子数组的长度

2.3.2.1 分析

因为数组只包含0和1, 可以将0全部换成-1. 那么问题就变成了 -1 和 1的数目相同, 此时子数组的和必定为0.

问题转换成了求子数组之和为0的最大长度.

2.3.2.2 题解

构造哈希表, key: 前缀和(前i个元素之和), value: 当前下标 i
遍历数组:
1. 将0换成 -1, 计算前i项和 sum
2. 在哈希表中寻找 sum-k(k = 0)的下标j, 计算长度 i - (j + 1) +1即i - j, 并更新最大长度
3. 将sum存入哈希表
返回最大长度

func findMaxLength(nums []int) int {
	maxLen := 0

	m := make(map[int]int, len(nums))
    // 满足条件的当前子数组的下标 j, 用于计算长度
    // 长度: i-0+1 = i - (j+1) +1 => j = -1
	m[0] = -1
	sum := 0
	for i, n := range nums {
		if n == 0 {
			n = -1
		}
		sum += n
		if j, ok := m[sum]; ok {
            // nums[i] 到 nums[j+1]的长度
			maxLen = max(maxLen, i-j)
		} else {
			// 第一次和为 sum 的下标
			m[sum] = i
		}

	}

	return maxLen
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

m[0] 表示当前子数组满足条件, 那么长度为 i + 1, 所以设置下标 m[0] = -1
因为要记录的是下标, 所以只能记录第一次和为sum的下标i, 故 m[sum] = i

2.3.3 问题12: 左右两边数组和相等

LCR 012. 寻找数组的中心下标open in new window

输入整数数组.

若一个数字左边子数组的和与右边子数组的和相同, 返回下标
若存在多个下标, 返回最左边的
不存在则返回 -1

2.3.3.1 分析

扫描数组, 到第i个数字时, 和 $S_i = S_{i-1} + a_i$ ,那么左边的子数组之和为 $S_{i-1}=S_i-a_i$

右边子数组之和 $S=S_n-S_i$ , $S_n$ 为所有元素之和.

所以先计算一次所有元素之和, 在扫描一次数组即可.

2.3.3.2 题解

扫描数组, 计算总和 total
扫描数组:
1. 计算当前和 $S_i$
2. 左边和为 $S_i-a_i$ , 右边和为 $total-S_i$
3. 比较两边返回结果

由于是从左到右扫描数组, 故返回值一定是最左边的

func pivotIndex(nums []int) int {
	total := 0
	for i := range nums {
		total += nums[i]
	}

	sum := 0
	for i := range nums {
		sum += nums[i]
		if (sum - nums[i]) == (total - sum) {
			return i
		}
	}

	return -1
}

2.3.4 问题13: 二维子矩阵的数字之和

输入二维矩阵, 计算给定左上角坐标到右下角坐标的子矩阵的数字之和.

计算数字之和的函数将被调用多次.

LCR 013. 二维区域和检索 - 矩阵不可变open in new window

2.3.4.1 分析

若计算函数直接进行计算, 那么时间复杂度为 O(mn), 又因计算函数将被调用多次, 此时效率将大大降低.

因此, 需要引入辅助矩阵来将子矩阵之和缓存起来, 调用计算函数时可直接使用缓存数据以提高效率.

对于矩阵m, 假设坐标(0, 0)到(r, c) 的子矩阵之和记为 $sums[r][c]$ .

那么坐标 $(r_1, c_1)$ 到 $(r_2, c_2)$ 的子矩阵之和 $S$ 可以由以下方式计算:

$S = sums[r_2][c_2] - sums[r_2][c_1-1] - sums[r_1-1][c_2] + sums[r_1-1][c_1-1]$

那么可以构造辅助矩阵 sums, 扫描原矩阵将计算结果存入辅助矩阵.

实际上也是利用前缀和的方式, 这次是二维的前缀和

2.3.4.2 题解

type NumMatrix struct {
	sums [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	m := len(matrix)
	if m == 0 {
		return NumMatrix{}
	}
	n := len(matrix[0])
	sums := make([][]int, m+1)
	sums[0] = make([]int, n+1)
	for r := range matrix {
		sums[r+1] = make([]int, n+1)
		for c := range matrix[r] {
			sums[r+1][c+1] = sums[r+1][c] + sums[r][c+1] - sums[r][c] + matrix[r][c]
		}
	}

	return NumMatrix{sums: sums}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	sums := this.sums
	return sums[row2+1][col2+1] - sums[row2+1][col1] - sums[row1][col2+1] + sums[row1][col1]
}

辅助矩阵比原矩阵多一行和列, 可以避免判断参数坐标为0(导致下标为-1)的情况

Reference

剑指Offer（专项突破版）open in new window

昵称

邮箱

网址

按正序
按倒序
按热度

2.3 累加数组数字求子数组之和

# 2.3.1 问题10: 和为 k 的子数组

# 2.3.1.1 分析&题解

# 暴力解法 TC: O(n3n^3n3)

# 暴力解法 - 优化 TC: O(n2n^2n2)

# HashTable TC: O(n) SC: O(n)

# 2.3.2 问题11: 0和1个数相同的子数组

# 2.3.2.1 分析

# 2.3.2.2 题解

# 2.3.3 问题12: 左右两边数组和相等

# 2.3.3.1 分析

# 2.3.3.2 题解

# 2.3.4 问题13: 二维子矩阵的数字之和

# 2.3.4.1 分析

# 2.3.4.2 题解

# Reference

预览: