领扣

Description

Given an array of integers, find how many pairs in the array such that their sum is less than or equal to a specific target number. Please return the number of pairs.

Example

Example 1:

Input: nums = [2, 7, 11, 15], target = 24.
Output: 5.
Explanation:
2 + 7 < 24
2 + 11 < 24
2 + 15 < 24
7 + 11 < 24
7 + 15 < 24

Example 2:

Input: nums = [1], target = 1.
Output: 0. 

sort数组之后，固定最长边，另外两边用LintCode 609. Two Sum - Less than or equal to target一样的方法可以求得（详细解释见）。代码如下：

class Solution:
    """
    @param S: A list of integers
    @return: An integer
    """
    def twoSum5(self, nums, target):
        # write your code here
        ans=0
        left,right=0,len(nums)-1
        while left<=right:
            while left<right and nums[left]+nums[right]<=target: left+=1
            ans+=right-left
            right-=1
        return(ans)

    def triangleCount(self, S):
        # write your code here
        if len(S)<3: return(0)
        S.sort()
        ans=0
        for j in range(2,len(S)):
            ans+=self.twoSum5(S[0:j], S[j])
        return(ans)