[Leet Code] 611. Valid Triangle Number

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.

 

 제한 사항

 

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

 

 입출력 예

 

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

 

 Python 코드

 

Python code 

class Solution(object):
    def triangleNumber(self, nums):

        nums, count, n = sorted(nums, reverse=1), 0, len(nums)
        for i in range(n):
            j, k = i + 1, n - 1
            while j < k:
                if nums[j] + nums[k] > nums[i]:
                    count += k - j
                    j += 1
                else:
                    k -= 1
        return count

* 참고 링크 : https://leetcode.com/problems/valid-triangle-number/discuss/104177/O(N2)-solution-for-C%2B%2B-and-Python

 

 C++ 코드

 

C ++ code

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        if(nums.size() < 3) return 0;
        sort(nums.begin(), nums.end(), greater<int>());
        int res = 0;
        int n = nums.size();
        for(int a = 0; a < n-2; ++a){
            int b = a+1;
            int c = n-1;
            while(b < c){
                if(nums[b] + nums[c] > nums[a]){
                    res = res + c - b;
                    ++b;
                }
                else
                    --c;
            }
        }
        return res;
    }
};

* 참고 링크 : https://www.programmerall.com/article/1415760413/

 

 출처

 

https://leetcode.com/problems/valid-triangle-number/