完整教程：【LeetCode 每日一题】2221. 数组的三角和

Problem:2221. 数组的三角和

文章目录

• 整体思路
• 完整代码
• 时空复杂度
• • 时间复杂度：O(N^2)
  • 空间复杂度：O(1)

整体思路

这段代码的目的是计算一个数组的“三角形和 (Triangular Sum)”。这个过程是模拟一个帕斯卡三角形（杨辉三角）的生成方式，但操作是加法后取模10，而不是单纯的加法。

具体过程是：从给定的 nums 数组开始，不断生成新的、长度减一的数组，新数组的每个元素是前一个数组相邻两个元素的和（对10取模）。这个过程一直持续，直到最后只剩下一个元素，这个元素就是最终的“三角形和”。

该算法采用了一种非常高效的原地计算 (in-place computation) 策略，直接在原始输入数组 nums 上进行迭代计算，从而避免了创建多个中间数组的开销。

1. 核心思想：逐层模拟

   • 算法的逻辑直接模拟了题目的要求。它将原始数组视为三角形的第一层（最底下一层）。
   • 之后，它一层一层地向上计算，每一层都比前一层少一个元素。
   • 例如，[1, 2, 3, 4, 5]
     • 第一轮计算后，数组变为 [3, 5, 7, 9]（只用了前4个位置）。
     • 第二轮后，变为 [8, 2, 6]（只用了前3个位置）。
     • 第三轮后，变为 [0, 8]（只用了前2个位置）。
     • 第四轮后，变为 [8]（只用了第1个位置）。
   • 最终的结果就是 8。

2. 原地实现：

   • 为了节省空间，算法直接在 nums 数组上进行操作。
   • 外层循环for (int i = n - 1; i > 0; i--)：
     • 该循环控制了总共要进行的轮数。i 代表当前正在处理的有效数组的长度减一（或者说，是最后一个有效元素的索引）。
     • 它从 n-1 开始，递减到 1。总共执行 n-1 轮计算。
   • 内层循环for (int j = 0; j < i; j++)：
     • 这个循环负责计算新一层的元素。
     • 在第 i 轮，它会遍历从 0 到 i-1 的所有索引 j。
     • nums[j] = (nums[j] + nums[j + 1]) % 10;: 这是核心的计算步骤。它用 nums[j] 和 nums[j+1] 的和（模10）来覆盖nums[j] 的原始值。
     • 当内层循环结束后，nums 数组的前 i 个元素 (nums[0] 到 nums[i-1]) 就构成了新一层的数组。

3. 返回结果：

   • 当外层循环结束时（i 已经递减到0），整个模拟过程完成。
   • 此时，经过 n-1 轮的计算，最终剩下的唯一一个元素就存储在 nums[0] 中，直接返回即可。

完整代码

class Solution {
/**
* 计算数组的三角形和。
* @param nums 输入的整数数组
* @return 最终的三角形和
*/
public int triangularSum(int[] nums) {
int n = nums.length;
// 外层循环控制计算的轮数。总共需要进行 n-1 轮。
// i 代表当前有效数组的最后一个元素的索引。
// i 从 n-1 递减到 1。
for (int i = n - 1; i > 0; i--) {
// 内层循环负责生成新一层的数组（长度为 i）。
// j 遍历当前层的相邻元素对。
for (int j = 0; j < i; j++) {
// 将 nums[j] 和 nums[j+1] 的和（模10）的结果
// 覆盖到 nums[j] 的位置上。
// 这样，在内层循环结束后，nums的前 i 个元素就是新一层的数组。
nums[j] = (nums[j] + nums[j + 1]) % 10;
}
}
// 经过 n-1 轮计算后，最终的结果就存储在 nums[0] 中。
return nums[0];
}
}

时空复杂度

• 设 N 是 nums 数组的长度。

时间复杂度：O(N^2)

1. 外层循环：for (int i = n - 1; i > 0; i--) 执行 N-1 次。
2. 内层循环：for (int j = 0; j < i; j++) 的执行次数依赖于外层循环的 i。
3. 总操作数：
   • 总的迭代次数是 (N-1) + (N-2) + ... + 1。
   • 这是一个等差数列求和，结果为 N * (N - 1) / 2。
   • 因此，核心计算语句 nums[j] = ... 被执行了 O(N^2) 次。

综合分析：
算法的时间复杂度由嵌套循环决定，为O(N^2)。

空间复杂度：O(1)

1. 主要存储开销：
   • 该算法完全在输入数组 nums 本身上进行操作，没有创建任何新的、与输入规模 N 成比例的数据结构。
   • 只使用了 n, i, j 等几个基本类型的变量。

综合分析：
算法所需的额外辅助空间是常数级别的。因此，其空间复杂度为O(1)。这是一个非常高效的原地算法。