原文链接: https://leetcode-cn.com/problems/running-sum-of-1d-array

英文原文

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

 

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

 

Constraints:

• 1 <= nums.length <= 1000
• -10^6 <= nums[i] <= 10^6

中文题目

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

 

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

示例 2：

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。

示例 3：

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]

 

提示：

• 1 <= nums.length <= 1000
• -10^6 <= nums[i] <= 10^6

通过代码

高赞题解

问题的算法思路太简单了，就不多说了。

但是，如果面试遇到这个问题，一个非常重要的事情是：问清楚面试官，是否可以修改传来的 nums 数组！

以这个问题的函数签名为例（C++）：

vector<int> runningSum(vector<int>& nums)

通常，这样设计的函数签名，是希望算法作者不修改 nums。否则，就不需要再返回一个 vector<int> 了。

当然，对于 C++ 来说，如果真的不希望算法作者修改 nums，下面这样设计函数签名更合理：

// 使用 const
vector<int> runningSum(const vector<int>& nums)

所以，对于这个问题，我更认可这样的实现：

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {

        vector<int> res(nums.size());
        res[0] = nums[0];
        for(int i = 1; i < nums.size(); i ++)
            res[i] = res[i - 1] + nums[i];
        return res;
    }
};

当然，从 OJ 判题的角度，这样就能 AC。

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {

        for(int i = 1; i < nums.size(); i ++)
            nums[i] += nums[i - 1];
        return nums;
    }
};

这就是 OJ 本身的局限性了。它只能考察到算法输出结果的正确性，而不能考察在算法设计上的考量。

如果面试遇到这个简单的问题，我认为和面试官沟通清楚这个 nums 能否修改更为重要。因为，这样一个简单的问题，面试官很可能期待的就是对这些实现细节的讨论，而非仅仅是给出一个结果。

其实，根据我的经验，在实际生产环境中，这样的函数设计，不改变传来的函数参数是常态。否则，相当于这个函数包含有 side-effect ：）

---

觉得有帮助请点赞哇！

统计信息

通过次数	提交次数	AC比率
130942	150651	86.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言