[611] Valid Triangle Number

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

• algorithms
• Medium (43.32%)
• Source Code: 611.valid-triangle-number.py
• Total Accepted: 34.5K
• Total Submissions: 77.3K
• Testcase Example: '[2,2,3,4]'

Given an array consists of non-negative integers, your task is to count 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: [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

Note:

The length of the given array won't exceed 1000. The integers in the given array are in the range of [0, 1000].

class Solution(object):
    def triangleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        lenn = len(nums)
        if lenn < 3: return 0

        nums.sort()
        count = 0
        for third in range(2, lenn)[::-1]:
            l, r = 0, third-1
            while l < r:
                if nums[l] + nums[r] <= nums[third]:
                    l += 1
                else:
                    count += r - l
                    r -= 1

        return count

#
# nums = [2,2,3,4]
# s = Solution()
# print s.triangleNumber(nums)