動機

two ptr!! 我忘了!!

Problem

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: 3Explanation: 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

 

Constraints:

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

sol1

列舉pair之後找下一個

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        return sum(bisect_left(nums[j+1:], nums[i]+nums[j])
            for i in range(len(nums)) for j in range(i+1, len(nums)))

sol2

two ptr!! 我忘了!!

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        count = 0
        L = len(nums)
        for i in range(L-1,1,-1):
            longest = nums[i]
            start = 0
            end = i - 1
            while start < end:
                if nums[start] + nums[end] > longest:
                    count += end - start
                    end -= 1
                else:
                    start += 1
        
        return count