###### tags: `Leetcode` `medium` `pointer` `python`

# 611. Valid Triangle Number

## [題目連結:] https://leetcode.com/problems/valid-triangle-number/

## 題目:
Given an integer array ```nums```, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

**Example 1:**

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

**Example 2:**

Input: nums = [4,2,3,4]
Output: 4

## 解題想法:
* 題目為: 要求輸出數組中所有能構成三角形的組合數
* 先排序好
* for迴圈從尾跑:固定最大值i
* two pointer:
* j=0
* k=i-1
* check nums[j]+nums[k]>nums[i]表示合格
* **res+= k-j**
* 累加k-j個，因為表示nums[j]~nums[k]之間的+nums[k]也一定大於nums[i]

## Python:

class Solution(object):
    def triangleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        res=0
        for i in range(len(nums)-1,1,-1): #i前面還須留兩個給jk
            j=0
            k=i-1
            while j<k:
                if nums[j]+nums[k]>nums[i]:
                    res+=k-j
                    k-=1 #目前組合夠大了，讓nums[k]小點試試
                else: #目前組合太小，讓nums[j]大點試試
                    j+=1
        return res

if __name__ =='__main__':
    result=Solution()
    ans=result.triangleNumber(nums = [4,2,3,4])
    print(ans)