382. 三角形计数

382. 三角形计数

中文English

给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形？

样例

样例 1:

输入: [3, 4, 6, 7]
输出: 3
解释:
可以组成的是 (3, 4, 6), 
           (3, 6, 7),
           (4, 6, 7)

样例 2:

输入: [4, 4, 4, 4]

背向型双指针:

class Solution:
    """
    @param S: A list of integers
    @return: An integer
    """
    def triangleCount(self, S):
        # write your code here
        #背向型双指针，首先固定一条边，大边，target，另外两条循环判断，看是否符合和 > target
        #如果符合，则说明right - left中间均是符合条件的，count += right - left,那么right减少值，看是否满足
        #如果不符合，left增大，也就是第一条边，看S[left] + S[right] > target,如果符合则继续计数
        
        l, count = len(S), 0
        S = sorted(S)
        
        #首选固定一条最长的边
        for i in range(l):
            target = S[i]
            
            #判断left和right两条边的值是否大于第三条边，如果大于，则中间的均大于,即[left,right] [left + 1,right]
            #...一直到left = right的时候均是大于的，符合条件]
            left, right = 0, i - 1
            while left < right:
                if (S[left] + S[right] > target):
                    count += right - left
                    
                    #继续right -= 1，看是否满足
                    right -= 1 
                else:
                    left += 1 
            
        return count