求数组的n到m项的和

说明

有一个数组 arr,求其 n 到 m 项的和，m>=n，比如[5, 4, -1, 10, 1, 2, 6, 9]，求其 2 到 7 项的和，即-1+10+1+2+6+9=27。

解法 1

构建一个二维的数组，想要获取 n 到 m 项的和，直接通过索引获取即可，改方法的好处就是构建一次二维数组，后续查找 n 到 m 项的和的复杂度位 1，也不需要进行额外的计算了。

func n2mSumWay1(arr []int64, n, m int64) int64 {
	table := make([][]int64, 0, len(arr))
	for i1, v1 := range arr {
		row := make([]int64, 0, len(arr))
		for i2, v2 := range arr {
			if i2 == i1 {
				row = append(row, v1)
			} else if i2 > i1 {
				row = append(row, v2+row[i2-1])
			} else {
				row = append(row, 0)
			}
		}
		table = append(table, row)
	}
	if m < n {
		panic("请输入合法的m和n，m必须大于等于n")
	}

	return table[n][m]
}

解法 2

构建一个前缀和数组 preArr

• 如果 n 是 0，获取 n 到 m 的和，返回该前缀和数组的第 m 项的值
• 如果 n 不是 0，获取 n 到 m 的和，返回 preArr[m]-preArr[n-1]的值

func n2mSumWay2(arr []int64, n, m int64) int64 {
	preArr := make([]int64, 0, len(arr))
	for i, v := range arr {
		if i == 0 {
			preArr = append(preArr, v)
		} else {
			preArr = append(preArr, preArr[i-1]+v)
		}
	}

	if n > m {
		panic("请输入合法的m和n，m必须大于等于n")
	}

	if n == 0 {
		return preArr[m]
	}

	return preArr[m] - preArr[n-1]
}