时间戳

首页 > 解决方案 > 查找数组中总和为给定值的所有元素对

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

问题描述

我陷入了以下问题描述的Hackerrank问题之一：-

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

例如，给定一个数组[1, 2, 3, 4]和一个目标值1，我们有三个满足条件的值：(2,1), (3,2), (4,3)。所以函数对应该返回 value 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

标签： pythonalgorithmdebugging

解决方案

这应该是一个 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

推荐阅读