611. Valid Triangle Number | LeetCode | Swift

題目

https://leetcode.com/problems/valid-triangle-number/description/?envType=daily-question&envId=2025-09-26

日期

2025/09/26

關鍵

• 因為題目要求找出合法的三角形，兩邊和要大於第三邊。意味著先把數列排序之後會比較好處理。

核心演算法

1. 開始走訪，主 index 所在的元素作為被拿來比較的最大數，從 index == 2 走到最後一個元素為止。
2. 接下來在該數左側的數列用雙指標找出合法的組合。

程式碼

好看版：GitHub

class Solution {
    func triangleNumber(_ nums: [Int]) -> Int {
        guard nums.count >= 3 else { return 0 }
        let nums = nums.sorted()
        var result = 0

        for index in (2..<nums.count) {
            var left = 0
            var right = index - 1

            while left < right {
                if nums[left] + nums[right] > nums[index] {
                    result += right - left
                    right -= 1
                } else {
                    left += 1
                }
            }
        }
        return result
    }
}