当前位置：首页 > news >正文

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

news 2026/3/26 20:35:16

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

Problem:2221. 数组的三角和

文章目录

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

整体思路

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

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

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

核心思想：逐层模拟
- 算法的逻辑直接模拟了题目的要求。它将原始数组视为三角形的第一层（最底下一层）。
- 之后，它一层一层地向上计算，每一层都比前一层少一个元素。
- 例如，[1, 2, 3, 4, 5]
  - 第一轮计算后，数组变为 [3, 5, 7, 9]（只用了前4个位置）。
  - 第二轮后，变为 [8, 2, 6]（只用了前3个位置）。
  - 第三轮后，变为 [0, 8]（只用了前2个位置）。
  - 第四轮后，变为 [8]（只用了第1个位置）。
- 最终的结果就是 8。
原地实现：
- 为了节省空间，算法直接在 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]) 就构成了新一层的数组。
返回结果：
- 当外层循环结束时（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];
}
}