Kotlin求解一维数组运行和：fold方案复杂度与foldIndexed用法解析

大家好，我目前正在学习数据结构，近期在尝试求解LeetCode上的算法题目。

题目内容 #

给定数组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]。

个人实现的解法 #

我自行编写的解法可正常运行，逻辑已完全理解，代码如下：

class Solution {
    fun runningSum(nums: IntArray): IntArray { 
        if (nums.size == 1) {
            return nums
        }
        for (index in 1..nums.size - 1) {
            nums[index] += nums[index - 1]
        }
        return nums
    }
}

复杂度分析 #

• 时间复杂度：O(n)，其中n为输入数组长度，因为仅通过单层循环遍历全数组完成运行和计算。
• 空间复杂度：O(1)，计算过程未使用额外空间（输出数组占用空间不计入复杂度统计）。

待解答的技术疑问 #

该解法逻辑验证无误，但我在题目讨论区看到了基于fold的Kotlin解法，现提出以下三个技术疑问：

1. 该fold解法与我编写的原始解法相比，复杂度是否存在变化？
2. 如果复杂度存在差异，请详细解释差异的具体原因；
3. 请解释foldIndexed函数的使用方法，我查阅官方文档后仍未完全理解其逻辑。

非常感谢解答。

内容的提问来源于stack exchange，提问作者Compose Learner