Подсчет количества пар в массиве с заданной разницей

Question

Я застрял в одной из проблем хакерранка со следующим описанием проблемы: -

Вам будет предоставлен массив целых чисел и целевое значение. Определите количество пар элементов массива, которые имеют разность, равную целевому значению.

Например, учитывая массив [1, 2, 3, 4] и целевое значение 1, мы имеем тризначения, удовлетворяющие условию: (2,1), (3,2) и (4,3). Таким образом, пары функций должны возвращать значение 3.

Мы должны реализовать функцию пар со следующими параметрами: -

k: an integer, the target difference
arr: an array of integers

Ограничения: -

1> Each Integer in arr[i] will be unique and positive.
2> target k will also be positive.

Моя нижеприведенная реализация функции не выполнена ни в одном из 18 тестовых случаев. Может кто-нибудь, пожалуйста, помогите мне отладить проблему: -

def binSearch(target,arr):
    lower = 0
    upper = len(arr)-1
    while lower <= upper:
        mid = int((lower + upper)/2)
        if(arr[mid] == target):
            return 1
        elif(arr[mid] > target):
            upper = mid - 1
        elif(arr[mid] < target):
            lower = mid + 1
    return -1

def pairs(k, arr):
    arr.sort()
    count = 0
    for i in range(len(arr)):
        target = abs(arr[i] - k)
        if(arr[i] == target):
            pass
        elif(binSearch(target,arr) == 1):
            count += 1
    return count

Answer 1

Это должно быть решение O (n) (где n - размер arr). Сначала преобразуйте массив в набор. Затем выполните итерацию каждого значения в arr и проверьте, находится ли arr + k в наборе, то есть разница между другим значением и текущим значением val равна k. Если это так, увеличьте counter на единицу.

def pairs(k, arr):
    counter = 0
    set_arr = set(arr)
    for val in arr:
        if val + k in set_arr:
            counter += 1
    return counter