Big meal count (time complexity) -- leetcode daily question

Title Description

Example

Their thinking

The problem is simple , Finding statistics in an array and adding two numbers is 2 Group number of powers of

The difficulty is how to find the right two numbers in an array of 100000 numbers

1. The first point is also easy to think of , The hash table will record the number of meals with the same delicious degree , This will slightly reduce the size of the target array

2. Record different tastes in the array , And sort . The purpose of this is to facilitate us to traverse the array in reverse order , This can avoid repetition caused by different order

3. according to a+b=c,c-a=b The principle is to directly query whether there is a target in the hash table , First, set the upper limit Double the current value 2 The logarithmic +1, Delimit the lower limit Double the current value 2 The logarithmic , Of course, it should be converted to an integer . Then traverse the integer between the upper and lower bounds , According to the changing c, Use c-a Look for b

4. find b Remember to multiply the values of the two hash tables

5. When double a number, it happens to be 2 And the number of meals is greater than 1, It is also what we need to record , It is necessary to add judgment to the program .

Code

Python Realization

import math
class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        hasmap = dict()
        for i in deliciousness:
            if i not in hasmap:
                hasmap[i] = 1
            else:
                hasmap[i] += 1
        answer=0
        l=sorted(list(hasmap.keys()))
        for i in range(len(l)-1,-1,-1):
            if l[i]>0:
                Max=int(math.log(l[i]*2,2))+1
                Min=int(math.log(l[i],2))
                for j in range(Min,Max+1):
                    temp=2**j-l[i]
                    if temp in hasmap and temp!=l[i] and temp<l[i]:
                        answer += hasmap[l[i]] * hasmap[temp]
                if l[i] != 0:
                    if math.log(2 * l[i], 2) % 1 == 0:
                        answer += (hasmap[l[i]] * (hasmap[l[i]] - 1) // 2)
        return answer%(10**9+7)

Shortcomings are welcome to be pointed out in the comment area