python - 查找数组中总和为给定值的所有元素对

Question

我陷入了 Hackerrank 问题之一，问题描述如下:-

您将获得一个整数数组和一个目标值。确定差值等于目标值的数组元素对的数量。

例如，给定一个数组[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