題目資訊

• 題目編號: 3024
• 題目連結: Type of Triangle
• 主題: Array, Math, Sorting

題目敘述

你被給予一個0-索引的整數陣列 nums，其大小為 3 且可以形成三角形的邊。

• 如果一個三角形的所有邊長相等，則稱之為正三角形。
• 如果一個三角形有且只有兩個邊長相等，則稱之為等腰三角形。
• 如果一個三角形的所有邊長均不同，則稱之為不等邊三角形。

返回一個代表 所能形成三角形類型的字串，如果不可形成三角形則返回 "none"。

範例 1:

輸入: nums = [3,3,3]
輸出: "equilateral"
解釋: 由於所有的邊長都相等，因此它將形成一個正三角形。

範例 2:

輸入: nums = [3,4,5]
輸出: "scalene"
解釋: 
nums[0] + nums[1] = 3 + 4 = 7，大於 nums[2] = 5。
nums[0] + nums[2] = 3 + 5 = 8，大於 nums[1] = 4。
nums[1] + nums[2] = 4 + 5 = 9，大於 nums[0] = 3。
由於在所有三種情況下，兩邊之和大於第三邊，因此可以形成三角形。
由於所有邊長均不同，它將形成一個不等邊三角形。

限制條件:

• nums.length == 3
• $1 \leq nums[i] \leq 100$

直覺

此問題要求確定由三個給定邊長所組成的三角形類型。三角形可根據邊長的相等性分類為：等邊三角形（三邊皆相等）、等腰三角形（兩邊相等）及不等邊三角形（三邊皆不相等）。除此之外，如果邊長不滿足三角形不等式定理，則可能無法形成三角形。因此，我的初步想法是利用這些性質來識別三角形的類型或確定是否不存在有效的三角形。

解法

為了解決此問題，採取以下步驟：

1. 排序邊長：我們首先對邊長數組進行排序。這使得檢查三角形不等式定理變得簡單。該定理指出，對於任意三角形，任意兩邊之和必須大於或等於剩餘一邊的長度。通過排序，這種檢查在遞增順序中得以簡化。

2. 檢查三角形的有效性：排序後，我們使用三角形不等式定理來驗證這些邊長能否形成有效的三角形。具體而言，如果兩個較小的邊之和不大於最大邊 ($sides[0] + sides[1] \leq sides[2]$)，那麼這些邊長無法組成三角形，我們返回「none」。

3. 分類三角形：

   • 等邊三角形：如果三條邊都相等 ($sides[0] == sides[1] == sides[2]$)，該三角形為等邊三角形。
   • 等腰三角形：如果只有兩條邊相等 ($sides[0] == sides[1]$，$sides[1] == sides[2]$，或 $sides[0] == sides[2]$)，則為等腰三角形。
   • 不等邊三角形：如果沒有邊相等，則該三角形為不等邊三角形。

此方法有效地確定三角形的類型，因為輸入的邊長數量是固定的，只有三個，因此可以簡單應用幾何原則和案例分析。

程式碼

C++

class Solution {
public:
    string triangleType(vector<int>& sides) {
        // 將邊長排序以簡化比較邏輯
        sort(sides.begin(), sides.end());
        
        // 檢查給定的邊長是否可以構成三角形
        // 這遵循三角形不等式定理
        if (sides[0] + sides[1] <= sides[2]) {
            return "none"; // 不是有效的三角形
        }
        
        // 檢查等邊三角形：所有邊都相等
        if (sides[0] == sides[1] && sides[1] == sides[2]) {
            return "equilateral";
        }
        
        // 檢查等腰三角形：只有兩個邊相等
        if (sides[0] == sides[1] || sides[1] == sides[2] || sides[0] == sides[2]) {
            return "isosceles";
        }
        
        // 如果以上都不是，則必為不等邊三角形：所有邊都不同
        return "scalene";
    }
};

Python

class Solution:
    def triangleType(self, sides):
        # 將邊長排序以簡化比較邏輯
        sides.sort()
        
        # 檢查給定的邊長是否能形成一個三角形
        # 這遵循三角不等式定理
        if sides[0] + sides[1] <= sides[2]:
            return "none"  # 不是一個有效的三角形
        
        # 檢查是否為等邊三角形：所有邊都相等
        if sides[0] == sides[1] and sides[1] == sides[2]:
            return "equilateral"
        
        # 檢查是否為等腰三角形：正好兩邊相等
        if sides[0] == sides[1] or sides[1] == sides[2] or sides[0] == sides[2]:
            return "isosceles"
        
        # 如果以上都不是，則必須是一般三角形：所有邊都不同
        return "scalene"

複雜度分析

• 時間複雜度: $O(1)$

  該程式碼操作於具有固定大小為3的輸入陣列 sides，此大小由問題約束指定。對於大小為 $n$ 的輸入，sort 操作的時間複雜度通常為 $O(n \log n)$，但由於 $n$ 是一個常數（在此情況下為3），因此實際上成為 $O(1)$。所有後續操作涉及簡單的算術運算和比較，這些都是常數時間操作。因此，整體時間複雜度仍然是 $O(1)$。

• 空間複雜度: $O(1)$

  空間複雜度是 $O(1)$，因為該演算法僅使用固定數量的額外空間。除了輸入陣列外，沒有使用其他的資料結構，而且所執行的操作不需要隨輸入大小增長的額外空間。