# 611. Valid Triangle Number
###### tags: `leetcode` `611` `medium` `rewrite`

## :memo: Question


## :memo: 題意
* 給你一串數列，讓你找出可以拼成一個三角形的三個邊，回傳有多少個。
* 我原本的寫法是用 dfs 會 TLE
* 我原本的想法是 他給你一個 list 那我們就只用 permutation 全部排列組合列出來。
## :memo: my solution code

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
    
        nums.sort()
        self.ans = 0
        self.dfs(nums, [])
        return self.ans

    
    def dfs(self, nums, res):
        if len(res) == 3:
            if res[0]+res[1] > res[2]:
                self.ans += 1
            return 
        
        if not nums and len(res) < 3:
            return
        
        for i in range(len(nums)):
            self.dfs(nums[i+1:], res + [nums[i]])

## :memo: leetcode solution code

* 思考: 要組合成一個三角形的邊的話，其他兩個邊要怎麼一定要符合 a + b > c，那最重要的是第三個邊，那我們有沒有可能用 c 去找出其他兩個符合的邊。

## :memo: leetcode solution code

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
    
        nums.sort()
        count = 0
        # i = 最後一個數字（也是代表最大的邊）
        # l = 最小的邊, r = 第二個邊
        
        for i in range(len(nums)-1, 1, -1):
            l = 0
            r = i - 1
            
            while l < r:
                # 如果這種情況發生，表示 l 之後不管移到哪個位置 都可以和 nums[r] 之和 大於 nums[i]
                if nums[l] + nums[r] > nums[i]:
                    count += r - l
                    r -= 1
                else:
                    l += 1
        return count

## :memo: bigO
* 時間複雜度: n log n + n^2
* 空間複雜度: log n (sorting)