題目連結(https://leetcode.com/problems/valid-triangle-number/description/?envType=daily-question&envId=2025-09-26)

每日一題，雙指針的進階版

1. Repeat（題目重複確認）

• 輸入：整數陣列  nums
• 輸出：整數（能組成三角形的三元組數量）
• 前提：
  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

2. Examples（舉例確認理解）

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are:
2,3,4 (using the first 2) 不同的2視為不同組合
2,3,4 (using the second 2)
2,2,3

3. Approach（解題思路）

方法 1：暴力法

• 先排序，再遍歷所有組合 (i, j, k) 其中 i < j < k
• 排序後只需檢查 nums[i] + nums[j] > nums[k]
• 時間複雜度：O(n^3)
• 空間複雜度：O(1)

方法 2：雙指針法

• 固定最大邊 nums[k]，用雙指針 i, j 在剩餘元素中尋找滿足條件的組合
• j 為 k - 1 ，i 從 0 開始，視情況移動 i, j
• 當 nums[i] + nums[j] > nums[k] 時，說明從 i 到 j-1 的所有元素都能與 nums[j], nums[k] 組成三角形
• 時間複雜度：O(n^2)
• 空間複雜度：O(1)

4. Code（C++）

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int result = 0;
        int n = nums.size();
        if(n < 3) return 0;

        for(int i = 0; i < n - 2; i++){
            for(int j = i+1; j < n - 1; j++){
                for(int k = j+1; k < n; k++){
                    if(nums[i] + nums[j] > nums[k]) result += 1;
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int result = 0;
        int n = nums.size();
        if(n < 3) return 0;

        for(int k = n-1; k>=2; k--){
            int i = 0, j = k-1;  //從 k 比小一位的地方開始檢查
            while(j > i){
                if(nums[i] + nums[j] > nums[k]){
                    result += j-i; //因為最小的i都有三角形了，中間的i+1, i+2...必可以建構出三角形
                    j--;
                }
                else{
                    i++;
                }
            }
        }
        return result;
     }
};

5. Test 範例

void test() {
    Solution sol;
    
    // Test Case 1
    vector<int> nums1 = {2,2,3,4};
    assert(sol.triangleNumber(nums1) == 3);
    
    // Test Case 2
    vector<int> nums2 = {4,2,3,4};
    assert(sol.triangleNumber(nums2) == 4);
    
    // Edge Cases
    vector<int> nums3 = {1};           // 長度 < 3
    assert(sol.triangleNumber(nums3) == 0);
    
    vector<int> nums4 = {1,2};         // 長度 < 3
    assert(sol.triangleNumber(nums4) == 0);
    
    vector<int> nums5 = {1,1,3};       // 1+1 < 3，無法組成三角形
    assert(sol.triangleNumber(nums5) == 0);
    
    vector<int> nums6 = {3,4,5};       // 一個有效三角形
    assert(sol.triangleNumber(nums6) == 1);
}

6. 相關題目與延伸概念

• 15. 3Sum - 雙指針基礎題
• 16. 3Sum Closest - 雙指針變化
• 18. 4Sum - 多指針擴展
• 259. 3Sum Smaller - 類似邏輯

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

• 重複問題： j 如果從 1 開始而不是從 i+1 開始，會造成重複計算。正確做法是確保 i < j < k。
• 排序的重要性：排序後可以簡化三角形判斷條件。對於排序後的 a ≤ b ≤ c，只需檢查 a + b > c
• 關於 HashMap：雖然可以用 map<tuple<int,int,int>, int> 來存三個變數，但在這個問題中不是最佳方案，因為會增加時間和空間複雜度。

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