Description

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person. 

Person A will NOT friend request person B (B != A) if any of the following conditions are true:

    age[B] <= 0.5 * age[A] + 7
    age[B] > age[A]
    age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.

Note that if A requests B, B does not necessarily request A.  Also, people will not friend request themselves.

How many total friend requests are made?

Example

Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.

Note

    1 <= ages.length <= 20000.
    1 <= ages[i] <= 120.

Code

Wrong Solution

class Solution(object):
    def numFriendRequests(self, ages):
        """
        :type ages: List[int]
        :rtype: int
        """
        
        N = len(ages)
        nums = [0]*121
        
        for i in ages:
            nums[i] += 1
            
        dp =  [0]*121
        for i in range(1, 121):
            dp[i] = dp[i-1] + nums[i]
        
        ret = 0
        
        for i in range(120, 0, -1):
            if nums[i] == 0:
                continue
            ret += nums[i]*(nums[i]-1)  // 在过滤条件前修改数据，我的思维习惯不是很干净
            th = i//2 + 7
            if th >= i:
                continue
            ret += nums[i]* (dp[i-1] - dp[th])
            
      
        
       
        return ret


AC Solution
class Solution(object):
    def numFriendRequests(self, ages):
        """
        :type ages: List[int]
        :rtype: int
        """
        
        N = len(ages)
        nums = [0]*121
        
        for i in ages:
            nums[i] += 1
            
        dp =  [0]*121
        for i in range(1, 121):
            dp[i] = dp[i-1] + nums[i]
        
        ret = 0
        
        for i in range(120, 0, -1):
            if nums[i] == 0:
                continue
            th = i//2 + 7
            if th >= i:
                continue
            ret += nums[i]*(nums[i]-1)
            ret += nums[i]* (dp[i-1] - dp[th])
            
        return ret
        

Leetcode: 825. Friends Of Appropriate Ages