python - 用递归找出一对中的目标差异

Question

给定一个未排序整数列表和一个目标整数，找出列表中任何对的差值是否与递归的目标整数相等。

>>> aList = [5, 4, 8, -3, 6]
>>> target = 9
return True

>>> aList = [-1, 5, 4]
>>> target = 3
return False

For 和 while 循环是不允许的。

不允许导入。

.sort() 是不允许的。

我试过这个，但没有用。

def calculate(aList, target):

    if len(aList) == 0 and diff != 0:
        return False

    startIndex = 0
    endIndex = len(aList) - 1

    return resursive_sum(aList, target, startIndex, endIndex)

def resursive_sum(aList, targ, start, end):

    print(f'Start: {start}')
    print(f'End: {end}')

    if start == end:
        return False
    elif aList[end] - aList[start] == targ:
        return True
    elif aList[end] - aList[start] < targ:
        return resursive_sum(values, targ, start, end - 1)
    return resursive_sum(aList, targ, start + 1, end)

如果我们不能使用循环对列表进行排序，我不确定如何解决这个问题。即使我们可以使用递归对列表进行排序，递归看起来应该如何才能扫描每一对的差异？

Answer 1

所以我实际上实现了它，但出于教育目的，我不会在稍后发布它(我将在几个小时内更新它)，因为我认为这是用于类或其他一些你应该弄清楚的设置靠你自己。
假设您正在尝试达到不同的目标 t = 5 并且您正在评估任意元素 8 。只有两个值允许 8 在集合中具有补码: 8 + 5 = 13 和 8 - 5 = 3 。
如果 3 或 13 已经在任何先前的元素中，您就会知道该集合有一对补码。否则，您需要记录 8 已被看到的事实。因此，如果稍后找到 3，则将查询 8 作为 3 + 5 = 8 将被考虑。
换句话说，我提出了一种方法，您可以递归地遍历列表，然后

(base case) 位于列表末尾

有一个当前元素 a 使得 a + t 或 a - t 已经被看到

记录当前元素已经被看到并跳转到下一个元素

理想情况下，这在最坏的情况下应该具有 O(n) 时间复杂度和 O(n) 空间复杂度(假设通过引用传递或类似的有效实现，并且还摊销了常量时间集查询)。它也可以使用基本数组来实现，但我不会说那更好(在 python 中)。
我会在几个小时内发布我的解决方案。祝你好运!

编辑 1: 希望你有足够的时间让它工作。我描述的方法可以如下完成:

def hasDiffRecur(L, t, i, C):
    """
    Recursive version to see if list has difference
    :param L: List to be considered
    :param t: Target difference
    :param i: Current index to consider
    :param C: Cache set
    """
    # We've reached the end. Give up
    if i >= len(L): 
        return False
    
    print(f" > L[{i}] = {L[i]:2}; is {L[i]-t:3} or {L[i]+t:2} in {C}")
    
    # Has the complement been cached?
    if L[i] - t in C: 
        print(f"! Difference between {L[i]} and {L[i]-t} is {t}")
        return True
    
    if L[i] + t in C: 
        print(f"! Difference between {L[i]} and {L[i]+t} is {t}")
        return True
    
    # Complement not seen yet. Cache element and go to next element
    C.add(L[i])
    return hasDiffRecur(L, t, i+1, C)

###################################################################

def hasDiff(L, t):
    """
    Initialized call for hasDiffRecur. Also prints intro message. 
    See hasDiffRecur for param info
    """
    print(f"\nIs a difference of {t} present in {L}?")
    return hasDiffRecur(L, t, 0, set())

###################################################################

hasDiff([5, 4, 8, -3, 6], 9)
hasDiff([-1, 5, 4], 3)
hasDiff([-1, 5, 4, -1, 7], 0) # If concerned about set non-duplicity 

输出:

Is a difference of 9 present in [5, 4, 8, -3, 6]?
 > L[0] =  5; is  -4 or 14 in set()
 > L[1] =  4; is  -5 or 13 in {5}
 > L[2] =  8; is  -1 or 17 in {4, 5}
 > L[3] = -3; is -12 or  6 in {8, 4, 5}
 > L[4] =  6; is  -3 or 15 in {8, -3, 4, 5}
! Difference between 6 and -3 is 9

Is a difference of 3 present in [-1, 5, 4]?
 > L[0] = -1; is  -4 or  2 in set()
 > L[1] =  5; is   2 or  8 in {-1}
 > L[2] =  4; is   1 or  7 in {5, -1}

Is a difference of 0 present in [-1, 5, 4, -1, 7]?
 > L[0] = -1; is  -1 or -1 in set()
 > L[1] =  5; is   5 or  5 in {-1}
 > L[2] =  4; is   4 or  4 in {5, -1}
 > L[3] = -1; is  -1 or -1 in {4, 5, -1}
! Difference between -1 and -1 is 0

编辑 2:
这是一个非常聪明和有效的解决方案。我确实意识到，这可能是根本不允许任何遍历的意图(即不存在查询集合)。如果是这种情况，上述方法可以通过一个固定大小的列表来完成，该列表预先分配的大小等于列表值的范围。
如果预先分配到列表范围的大小的概念仍然是太多迭代，我可以想到递归实现的穷举方法。对此可能有一种更有效的方法，但您可以将问题归结为类似双循环的问题(O(n^2) 时间复杂度)。这是一个微不足道的算法，我认为你可以在没有文档的情况下理解它，所以我会把它放在那里完成:

def hasDiffRecur(L, t, i = 0, j = 1):
    if i >= len(L): return False
    if j >= len(L): return hasDiffRecur(L, t, i+1, i+2)
    if abs(L[i] - L[j]) == t: return True
    return hasDiffRecur(L, t, i, j+1)

###################################################################

print(hasDiffRecur([5, 4, 8, -3, 6], 9))  # True
print(hasDiffRecur([-1, 5, 4], 3))        # False
print(hasDiffRecur([-1, 5, 4, -1, 7], 0)) # True