这个问题是在Google的编程面试中提出的。我想到了两种方法：
找到所有长度为n的子序列，计算两个元素的和并检查它是否等于k。如果是，则打印Yes，否则继续搜索。这是一种暴力的方法。
将数组按非递减顺序排序。然后从其右侧开始遍历数组。假设我们有一个已排序的数组{3,5,7,10}，我们想让总和为17。我们将从元素10开始，索引=3，用“j”表示索引。然后包括当前元素并计算required_sum = sum-current_element。之后，我们可以在array [0-(j-1)] 中执行二元或三元搜索，以查找其值等于required_sum的元素。如果我们找到这样的元素，那么我们可以停止搜索，因为我们已经找到了一个长度为2且总和为给定总和的子序列。如果我们没有找到这样的元素，则将j的索引减小，并针对长度为length-1的结果子数组（在这种情况下排除索引3处的元素）重复上述步骤。
这里我们考虑到数组可能包含负数和正数整数。
您能推荐比这更好的解决方案吗？也许是DP方案？一个能进一步减少时间复杂度的解决方案。
package ArrayPractice;
import java.util.Scanner;
public class Question5 {
public boolean cons(int[] test) {
for (int i = 0; i < test.length; i++) {
for (int j = i + 1; j < test.length; j++) {
if (test[i] == test[j]) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the array range: ");
int x = sc.nextInt();
int[] testing = new int[x];
for (int y = 0; y < testing.length; y++) {
System.out.println("Enter the Array number: " + y);
testing[y] = sc.nextInt();
}
Question5 question5 = new Question5();
System.out.println(question5.cons(testing));
}
}
func findTwoSumSorted(inputArray: [Int], sum: Int) {
let sortedArray = inputArray.sorted()
var leftIndex = 0
var rightIndex = sortedArray.count - 1
while leftIndex < rightIndex {
let leftElement = sortedArray[leftIndex]
let rightElement = sortedArray[rightIndex]
let currentSum = leftElement + rightElement
if currentSum == sum {
print("(\(leftElement), \(rightElement))")
return
} else if currentSum < sum {
leftIndex += 1
} else {
rightIndex -= 1
}
}
}
Javascript答案为O(n)
function checkPair(arr, n) {
for (var i in arr) {
if (arr.includes(n - arr[i])) {
return true;
}
}
return false;
}
var a = [4,2,8,7,5,77,6,3,22];
var n = 99;
var m = 100;
console.log(checkPair(a, n));
console.log(checkPair(a, m));[1,2]和2应该返回false的情况；换句话说，你不能只是将一个数字加倍，因为它指定了“任意两个”）。def do_they_add(terms, result):
first_terms = []
for second_term in terms:
for first_term in first_terms:
if second_term + first_term == result:
return True
first_terms.append(second_term)
return False
这个函数从结果开始逐个减去每个数，直到差值在给定的列表中出现（使用规则a + b = c -> c-a = b）。使用enumerate和奇数索引是为了排除当前值，符合本答案第一句话的要求。
def do_they_add_alt(terms, result):
for i, term in enumerate(terms):
diff = result - term
if diff in [*terms[:i - 1], *terms[i + 1:]]:
return True
return False
如果您允许将一个数字加到它本身，那么第二种实现方式可以简化为：
def do_they_add_alt(terms, result):
for term in terms:
diff = result - term
if diff in terms:
return True
return False
此函数接受两个参数并循环遍历列表的长度，在循环内部有另一个循环，它将一个数字添加到列表中的其他数字，并检查它们的总和是否等于k。
const list = [10, 15, 3, 7];
const k = 17;
function matchSum(list, k){
for (var i = 0; i < list.length; i++) {
list.forEach(num => {
if (num != list[i]) {
if (list[i] + num == k) {
console.log(`${num} + ${list[i]} = ${k} (true)`);
}
}
})
}
}
matchSum(list, k);
我对每日编程问题的答案
# Python 2.7
def pairSumK (arr, goal):
return any(map(lambda x: (goal - x) in arr, arr))
arr = [10, 15, 3, 7]
print pairSumK(arr, 17)
我使用Scala实现了
def hasSome(xs: List[Int], k: Int): Boolean = {
def check(xs: List[Int], k: Int, expectedSet: Set[Int]): Boolean = {
xs match {
case List() => false
case head :: _ if expectedSet contains head => true
case head :: tail => check(tail, k, expectedSet + (k - head))
}
}
check(xs, k, Set())
}
我已经尝试了Go语言中的解决方案。然而，它需要O(n^2)的时间。
package main
import "fmt"
func twoNosAddUptoK(arr []int, k int) bool{
// O(N^2)
for i:=0; i<len(arr); i++{
for j:=1; j<len(arr);j++ {
if arr[i]+arr[j] ==k{
return true
}
}
}
return false
}
func main(){
xs := []int{10, 15, 3, 7}
fmt.Println(twoNosAddUptoK(xs, 17))
}
这是Python 3.7中具有O(N)复杂度的代码：
def findsome(arr,k):
if len(arr)<2:
return False;
for e in arr:
if k>e and (k-e) in arr:
return True
return False
同时提供Python 3.7中O(N^2)复杂度的最佳代码：
def findsomen2 (arr,k):
if len(arr)>1:
j=0
if arr[j] <k:
while j<len(arr):
i =0
while i < len(arr):
if arr[j]+arr[i]==k:
return True
i +=1
j +=1
return False
使用vavr库，可以以非常简洁的方式完成：
List<Integer> numbers = List(10, 15, 3, 7);
int k = 17;
boolean twoElementsFromTheListAddUpToK = numbers
.filter(number -> number < k)
.crossProduct()
.map(tuple -> tuple._1 + tuple._2)
.exists(number -> number == k);
O(n)，空间复杂度也为O(n)的算法。对于每个元素，检查它是否存在于哈希表中。如果不存在，则将k-arr[i]存储起来，并继续下一个元素。 - thebenman