2221-数组的三角和

给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 0 到 9 之间（两者都包含）的一个数字。

nums 的 三角和 是执行以下操作以后最后剩下元素的值：

1. nums 初始包含 n 个元素。如果 n == 1 ， 终止 操作。否则， 创建 一个新的下标从 0 开始的长度为 n - 1 的整数数组 newNums 。
2. 对于满足 0 <= i < n - 1 的下标 i ，newNums[i] 赋值 为 (nums[i] + nums[i+1]) % 10 ，% 表示取余运算。
3. 将 newNums 替换 数组 nums 。
4. 从步骤 1 开始 重复 整个过程。

请你返回 nums 的三角和。

示例 1：

**输入：** nums = [1,2,3,4,5]
**输出：** 8
**解释：**
上图展示了得到数组三角和的过程。

示例 2：

**输入：** nums = [5]
**输出：** 5
**解释：**
由于 nums 中只有一个元素，数组的三角和为这个元素自己。

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

方法一：模拟

思路与算法

我们只需要按照题目中的操作进行模拟即可。

记数组 nums 的长度为 n。我们进行 n-1 次循环，第 i~(0 \leq i < n) 次循环得到 (\textit{nums}[i] + \textit{nums}[i+1]) \bmod 10 的值，并将其放去一个新的数组 new_nums 中。当循环结束后，我们再用 new_nums 覆盖 nums。

当 n=1 时，操作结束，我们返回 nums}[0] 即可。

代码

[sol1-C++]

class Solution {
public:
    int triangularSum(vector<int>& nums) {
        while (nums.size() > 1) {
            vector<int> new_nums;
            for (int i = 0; i < nums.size() - 1; ++i) {
                new_nums.push_back((nums[i] + nums[i + 1]) % 10);
            }
            nums = move(new_nums);
        }
        return nums[0];
    }
};

[sol1-Python3]

class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        while len(nums) > 1:
            new_nums = list()
            for i in range(len(nums) - 1):
                new_nums.append((nums[i] + nums[i + 1]) % 10)
            nums = new_nums
        return nums[0]

复杂度分析

• 时间复杂度：O(n^2)。

• 空间复杂度：O(n)，即数组 new_nums 需要使用的空间。