【算法】优化算法的常用方法，你不会不知道吧？

今天是 Kevin 的算法之路100天征程的第3天。为大家讲解 LeetCode 第 307 题，是一道简单难度的题目。

每日一笑

餐馆里一个厨师帮工姓蔡，其他人都习惯喊他小蔡，一天有几个客人来吃饭，还没有点菜就听他们喊：“老板，先上小菜。”结果老板就摇着头看着小蔡战战兢兢地走到这个客人的包间里。

题目描述

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 说明:

你可以假设数组不可变。 会多次调用 sumRange 方法。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/range-sum-query-immutable 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

方法一：暴力法

直接使用for循环将索引 i 到 j 之间的每个元素相加。不解释了，简单粗暴。

// Go type NumArray struct { data []int } func Constructor(nums []int) NumArray { return NumArray{nums} } func (this *NumArray) SumRange(i int, j int) int { sum := 0 for k:= i; k <=j; k++ { sum += this.data[k] } return sum } // Java private int[] data; public NumArray(int[] nums) { data = nums; } public int sumRange(int i, int j) { int sum = 0; for (int k = i; k <= j; k++) { sum += data[k]; } return sum; }

暴力法的最大缺点就是耗时，像这里的 sumRange 方法中有一层for循环，时间复杂度为 O(n)，题意又说会多次调用 sumRange 方法，所以调用 k 次的话，时间复杂度则为 O(kn) 。

这里的空间复杂度为 O(1)，请注意，data 是对 nums 的引用，不是它的副本。

我们在想想能不能优化一下呢～

方法二：缓存

我们可以提前计算出前 i 个数的和，即 a[i] 等于区间 [1,i] 的和，消耗时间为 O(n)

区间 [i,j] 的和求公式为：SumRange(i,j) = sum[j] - sum[i-1]，每次查询消耗时间为 O(1)，k 次查询时间复杂度为 O(k)

总的来说，时间复杂度为 O(n+k)

当然，这里用了数组来存储和的结果，自然多消耗了空间。这里空间复杂度为 O(n)。一般而言，很多优化都是以空间换时间的。

代码实现

// go type NumArray struct { sum []int // 存储[0,i]的和 } func Constructor(nums []int) NumArray { a := NumArray{} a.sum = append(a.sum, 0) // 初始化 sum 切片，sum[0]=0 // 遍历求sum[i] for i := 1; i <= len(nums); i++ { a.sum = append(a.sum, a.sum[i-1]+nums[i-1]) } return a } func (this *NumArray) SumRange(i int, j int) int { return this.sum[j+1] - this.sum[i] } // java class NumArray { private int[] sum; public NumArray(int[] nums) { sum = new int[nums.length + 1]; for (int i = 1; i <= nums.length; i++) { sum[i] = sum[i-1] + nums[i-1]; } } public int sumRange(int i, int j) { return sum[j + 1] - sum[i]; } }

郑重声明：

所展示代码已通过 LeetCode 运行通过，请放心食用～

在唠唠嗑

很多人都想养成好习惯，但大多数人却是三分钟热度。为了我们能一起坚持下去，决定制定如下计划（福利）

一起学算法，打卡领红包！

参与方式：

关注我的原创微信公众号「Kevin的学堂」，一起学习，一起更优秀！

打卡规则为：

「留言」“打卡XXX天” ➕「分享」到朋友圈

奖励：

连续打卡 21 天，联系本人获取 6.6 元红包一个！

连续打卡 52 天，联系本人获取 16.6 元红包一个！

连续打卡 100 天，联系本人获取 66.6 元红包一个！