一种递归算法，用于在数组中查找总和为给定整数的两个整数
我需要一个算法来确定一个数组是否包含两个与给定整数相加的元素。
数组已排序。
该算法应该是递归的并且在O（n）中运行。
递归步骤应该基于总和，这意味着方法传递总和并根据最终结果返回true或false（如果找到两个元素 – 返回true，否则返回false）
只能使用线性数据结构。
任何想法都赞赏..
您可以使用（例如） 尾递归将任何迭代算法转换为递归算法。 如果不是家庭作业，我会更加膨胀。 我想你会从另一篇文章中理解它。
通常我会使用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 ) { ... } 希望这是一个足够好的暗示。
我认为哈希是好的，例如，1,3,7,9,12,14,33 ……
如果我们想要sum = 21，我们将数字哈希到哈希表中，那么，O（n）。
我们迭代它们，当我们得到7时，我们让21-7 = 14，所以我们哈希14，我们可以找到它。 所以7 + 14 = 21，
我们得到了它！
这是一个考虑重复条目的解决方案。 它是用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=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; }
我在一家大公司的采访中解决了这个问题。 他们接受了但不是我。 所以这里适合所有人。
从arrays的两侧开始，慢慢向内工作，确保重复计算（如果存在的话）。
它只计算成对，但可以重做
- 使用递归
- 找对子
- 找对
- 找对> x
请享用！
对数组进行排序。 搜索每个数字的补码（总和数）。 复杂性O（nlogn）。