一个递归算法来查找数组中的两个整数，并将其相加成给定的整数

Question

我需要一种算法来确定一个数组是否包含两个和给定整数相加的元素。

该数组已排序。

该算法应该是递归并在O（n）中运行。

递归步骤应基于总和，这意味着该方法进入的总和，并返回真或假根据最终结果（如果两个元件被发现 - 返回true，否则 - 返回false）

只有可以使用线性数据结构。

任何想法表示赞赏..

Answer 1

您可以通过使用（例如）tail recursion任何迭代算法转换成递归之一。如果它不是作业，我会更加宽广。我想你会从另一篇文章中理解它。

Answer 2

对数组进行排序。搜索每个数字（和数）的补码。复杂度O（nlogn）。

Answer 3

通常我会使用一个Map，但由于其中一个要求是使用线性数据结构，所以我认为这是排除的，所以我会去使用布尔数组。

public boolean hasSum(int[] numbers, int target) 
{ 
    boolean[] hits = new boolean[ target + 1 ]; 
    return hasSumRecursive(0, numbers, target, hits); 
} 

public boolean hasSumRecursive(int index, int[] numbers, int target, boolean[] hits) 
{ 
    ... 
} 

希望这是一个足够好的提示。

Answer 4

我认为哈希是好的，例如，1,3,7,9,12,14,33 ...

如果我们想总和= 21，我们哈希数字到一个哈希表中，所以， ， 上）。

我们迭代它们，当我们得到7时，我们让21-7 = 14，所以我们散列14，我们可以找到它。所以7 + 14 = 21，

我们知道了！

Answer 5

这是一个解决方案女巫考虑到重复条目。它是用javascript编写的，并假定数组已排序。该解决方案在O（n）时间内运行，除了变量外不使用任何额外的内存。

var count_pairs = function(_arr,x) { 
    if(!x) x = 0; 
    var pairs = 0; 
    var i = 0; 
    var k = _arr.length-1; 
    if((k+1)<2) return pairs; 
    var halfX = x/2; 
    while(i<k) { 
    var curK = _arr[k]; 
    var curI = _arr[i]; 
    var pairsThisLoop = 0; 
    if(curK+curI==x) { 
     // if midpoint and equal find combinations 
     if(curK==curI) { 
     var comb = 1; 
     while(--k>=i) pairs+=(comb++); 
     break; 
     } 
     // count pair and k duplicates 
     pairsThisLoop++; 
     while(_arr[--k]==curK) pairsThisLoop++; 
     // add k side pairs to running total for every i side pair found 
     pairs+=pairsThisLoop; 
     while(_arr[++i]==curI) pairs+=pairsThisLoop; 
    } else { 
     // if we are at a mid point 
     if(curK==curI) break; 
     var distK = Math.abs(halfX-curK); 
     var distI = Math.abs(halfX-curI); 
     if(distI > distK) while(_arr[++i]==curI); 
     else while(_arr[--k]==curK); 
    } 
    } 
    return pairs; 
} 

我在一家大型企业的面试中解决了这个问题。他们拿走了它，但不是我。 所以这里是每个人。

从数组的两侧开始，慢慢地向内进行工作，确保存在重复数据。

它只能算作对，但可以修改，以

• 使用递归
• 找到对
• 找到对< X
• 找到对> X

享受！