題目連結(https://leetcode.com/problems/find-triangular-sum-of-an-array/description/?envType=daily-question&envId=2025-09-30)

You are given a 0-indexed integer array nums, where nums[i] is a digit between 0 and 9 (inclusive).

The triangular sum of nums is the value of the only element present in nums after the following process terminates:

1. Let nums comprise of n elements. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n - 1.
2. For each index i, where 0 <= i < n - 1, assign the value of newNums[i] as (nums[i] + nums[i+1]) % 10, where % denotes modulo operator.
3. Replace the array nums with newNums.
4. Repeat the entire process starting from step 1.

Return the triangular sum of nums.

今天每日一題雖然是medium，但比較偏 easy!

1. Repeat（題目重複確認）

• 輸入：整數陣列nums
• 輸出：經過定義與上述四個過程後得出的三角總和
• 前提：
  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 9

2. Examples（舉例確認理解）

• Input: nums = [1,2,3,4,5]
• Output: 8
• Explanation:
• The above diagram depicts the process from which we obtain the triangular sum of the array.

3. Approach（解題思路）

方法 1：遞迴

• 最先想到的是遞迴法，不斷去重複兩兩相加並取個位數的運算式，建新的陣列，然後不斷更新，但時間複雜度會比較久
• 時間複雜度：O(n²)
  • 第 1 層：處理 n-1 個元素
  • 第 2 層：處理 n-2 個元素
  • …
  • 總和：(n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)
• 空間複雜度：O(n²) 會用到n+n-1+n-2+…+1 = (n+1)*n/2

方法 2：迭代

• 直接在原本的陣列上改，不會需要額外的空間
• 時間複雜度：O(n²)
• 空間複雜度：O(1) 原地修改 (In-Place)

4. Code（C++）

class Solution {
public:
    int triangularSum(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        return sum(nums);
    }

private:
    int sum(vector<int>& nums){
        // 終止條件
        if(nums.size() == 1) return nums[0];
        
        // 創建新陣列
        vector<int> newNums(nums.size() - 1);
        
        // 計算相鄰和
        for(int i = 0; i < nums.size() - 1; i++){
            newNums[i] = (nums[i] + nums[i+1]) % 10;  // 修正：nums 而非 newnums
        }
        
        // 遞迴處理新陣列
        return sum(newNums);  // 修正：需要繼續遞迴
    }
};

class Solution {
public:
    int triangularSum(vector<int>& nums) {
        int n = nums.size();
        while(n > 1){ // 直接在原陣列上修改
            for(int i = 0; i < n - 1; i++) {
                nums[i] = (nums[i] + nums[i+1]) % 10;
            }
            n--; //改完後縮小陣列
        }
        return nums[0];
    }
};

5. Test 範例

nums = [1,2,3,4,5] 注意過程中陣列長度的變化

第一輪: [1, 2, 3, 4, 5]

↓

[3, 5, 7, 9] (1+2=3, 2+3=5, 3+4=7, 4+5=9)

第二輪: [3, 5, 7, 9]

↓

[8, 2, 6] (3+5=8, 5+7=12%10=2, 7+9=16%10=6)

第三輪: [8, 2, 6]

↓

[0, 8] (8+2=10%10=0, 2+6=8)

第四輪: [0, 8]

↓

[8] (0+8=8)

答案: 8

6. 相關題目與延伸概念

118. Pascal's Triangle I

119. Pascal's Triangle II

7. 補充：語法＆注意事項

巴斯卡三角形

模擬法

ps. 部分內容經 AI 協助整理