deeprun

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/