---
# System prepended metadata

title: 611. Valid Triangle Number
tags: [pointer, Leetcode, medium, python]

---

###### 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:
``` 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)
```