Google编程面试中提到了这个问题。我想到了两种相同的方法:
在这里,我们认为数组可能有负整数和正整数。
你能提出比这更好的解决方案吗? DP解决方案可能吗?一种可以进一步降低时间复杂度的解决方案。
借助于O(N)时间和空间复杂度的设置,可以很容易地解决这个问题。首先将数组的所有元素添加到集合中,然后遍历数组中的每个元素,并检查集合中是否存在K-ar [i]或不。
这是java中具有O(N)复杂度的代码:
boolean flag=false;
HashSet<Long> hashSet = new HashSet<>();
for(int i=0;i<n;i++){
if(hashSet.contains(k-ar[i]))flag=true;
hashSet.add(ar[i]);
}
if(flag)out.println("YES PRESENT");
else out.println("NOT PRESENT");
C ++解决方案:
int main(){
int n;
cin>>n;
int arr[n];
for(int i = 0; i < n; i++)
{
cin>>arr[i];
}
int k;
cin>>k;
int t = false;
for(int i = 0; i < n-1; i++)
{
int s = k-arr[i];
for(int j = i+1; j < n; j++)
{
if(s==arr[j])
t=true;
}
}
if (t){
cout<<"Thank you C++, very cool";
}
else{
cout<<"Damn it!";
}
return 0;
}
function check(arr,k){
var result = false;
for (var i=0; i < arr.length; i++){
for (var j=i+1; j < arr.length; j++){
result = arr[i] + arr[j] == k;
console.log(`${arr[i]} + ${arr[j]} = ${arr[i] + arr[j]}`);
if (result){
break;
}
}
return result;
}
的JavaScript。
蟒蛇
def add(num, k):
for i in range(len(num)):
for j in range(len(num)):
if num[i] + num[j] == k:
return True
return False
这是Python。上)。需要在循环时删除当前元素,因为列表可能没有重复的数字。
def if_sum_is_k(list, k):
i = 0
list_temp = list.copy()
match = False
for e in list:
list_temp.pop(i)
if k - e in list_temp:
match = True
i += 1
list_temp = list.copy()
return match
我想出了两个C ++解决方案。一个是天真的暴力类型,它在O(n ^ 2)时间内。
int main() {
int N,K;
vector<int> list;
cin >> N >> K;
clock_t tStart = clock();
for(int i = 0;i<N;i++) {
list.push_back(i+1);
}
for(int i = 0;i<N;i++) {
for(int j = 0;j<N;j++) {
if(list[i] + list[j] == K) {
cout << list[i] << " " << list[j] << endl;
cout << "YES" << endl;
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
return 0;
}
}
}
cout << "NO" << endl;
printf("Time taken: %f\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
return 0;}
您可以想象,此解决方案将在较高的输入值上花费大量时间。
我的第二个解决方案我能够在O(N)时间内实现。使用unordered_set,就像上面的解决方案一样。
#include <iostream>
#include <unordered_set>
#include <time.h>
using namespace std;
int main() {
int N,K;
int trig = 0;
int a,b;
time_t tStart = clock();
unordered_set<int> u;
cin >> N >> K;
for(int i = 1;i<=N;i++) {
if(u.find(abs(K - i)) != u.end()) {
trig = 1;
a = i;
b = abs(K - i);
}
u.insert(i);
}
trig ? cout << "YES" : cout << "NO";
cout << endl;
cout << a << " " << b << endl;
printf("Time taken %fs\n",(double) (clock() - tStart)/CLOCKS_PER_SEC);
return 0;
}
Javascript解决方案:
function hasSumK(arr, k) {
hashMap = {};
for (let value of arr) {
if (hashMap[value]) { return true;} else { hashMap[k - value] = true };
}
return false;
}
这里有两个非常快速的Python实现(考虑到[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
Python代码:
L = list(map(int,input("Enter List: ").split()))
k = int(input("Enter value: "))
for i in L:
if (k - i) in L:
print("True",k-i,i)
C#解决方案:
bool flag = false;
var list = new List<int> { 10, 15, 3, 4 };
Console.WriteLine("Enter K");
int k = int.Parse(Console.ReadLine());
foreach (var item in list)
{
flag = list.Contains(k - item);
if (flag)
{
Console.WriteLine("Result: " + flag);
return;
}
}
Console.WriteLine(flag);
我的C#实现:
bool isPairPresent(int[] numbers,int value)
{
for (int i = 0; i < numbers.Length; i++)
{
for (int j = 0; j < numbers.Length; j++)
{
if (value - numbers[i] == numbers[j])
return true;
}
}
return false;
}
这是一个Java实现,其时间复杂度与用于对数组进行排序的算法相同。请注意,这比第二个想法要快,因为每次检查数字时,我们都不需要搜索整个数组中的匹配伙伴。
public static boolean containsPairWithSum(int[] a, int x) {
Arrays.sort(a);
for (int i = 0, j = a.length - 1; i < j;) {
int sum = a[i] + a[j];
if (sum < x)
i++;
else if (sum > x)
j--;
else
return true;
}
return false;
}
通过诱导证明:令a [0,n]为长度为n + 1且p =(p1,p2)的阵列,其中p1,p2为整数,p1 <= p2(w.l.o.g。)。假设[0,n]包含p1和p2。在它没有的情况下,算法显然是正确的。
基本情况(i = 0,j = n):a [0,-1]不包含p1且a [n,n + 1]不包含p2。
假设:a [0,i-1]不包含[i]且[j + 1,n]不包含p2。
步骤案例(i到i + 1或j到j - 1):
由于在每次迭代时,[0,i-1]和[j + 1,n]不包含p1和p2,因此[i,j]确实包含p1和p2。最终a [i] = p1和a [j] = p2,算法返回true。
Python实现:代码将使用字典以O(n)复杂度执行。我们将(desired_output - current_input)存储为字典中的键。然后我们将检查字典中是否存在该数字。在字典中搜索的平均复杂度为O(1)。
def PairToSumK(numList,requiredSum):
dictionary={}
for num in numList:
if requiredSum-num not in dictionary:
dictionary[requiredSum-num]=0
if num in dictionary:
print(num,requiredSum-num)
return True
return False
arr=[10, 5, 3, 7, 3]
print(PairToSumK(arr,6))
使用Javascript
const findPair = (array, k) => {
array.sort((a, b) => a - b);
let left = 0;
let right = array.length - 1;
while (left < right) {
const sum = array[left] + array[right];
if (sum === k) {
return true;
} else if (sum < k) {
left += 1;
} else {
right -= 1;
}
}
return false;
}
这是一个javascript解决方案:
function ProblemOne_Solve()
{
const k = 17;
const values = [10, 15, 3, 8, 2];
for (i=0; i<values.length; i++) {
if (values.find((sum) => { return k-values[i] === sum} )) return true;
}
return false;
}
我用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 Lang尝试过这个解决方案。但是,它消耗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))
}
这个函数需要2个参数并循环遍历列表的长度,并且在循环内部还有另一个循环,它将一个数字添加到列表中的其他数字并检查总和是否等于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)
以下是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
以及具有O(N ^ 2)复杂度的Python 3.7中的最佳案例代码:
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
Javascript解决方案
function matchSum(arr, k){
for( var i=0; i < arr.length; i++ ){
for(var j= i+1; j < arr.length; j++){
if (arr[i] + arr[j] === k){
return true;
}
}
}
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)空间的java实现。这个想法有一个HashMap,它将包含每个数组元素w.r.t target的补充。如果找到补码,我们有2个数组元素,它们与目标相加。
public boolean twoSum(int[] nums, int target) {
if(nums.length == 0 || nums == null) return false;
Map<Integer, Integer> complementMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int curr = nums[i];
if(complementMap.containsKey(target - curr)){
return true;
}
complementMap.put(curr, i);
}
return false;
}
如果你想找对数,
pairs = [3,5,7,10]
k = 17
counter = 0
for i in pairs:
if k - i in pairs:
counter += 1
print(counter//2)
Potkhon Solyuion:
def FindPairs(arr, k):
for i in range(0, len(arr)):
if k - arr[i] in arr:
return True
return False
A = [1, 4, 45, 6, 10, 8]
n = 100
print(FindPairs(A, n))
要么
def findpair(list1, k):
for i in range(0, len(list1)):
for j in range(0, len(list1)):
if k == list1[i] + list1[j]:
return True
return False
nums = [10, 5, 6, 7, 3]
k = 100
print(findpair(nums, k))
使用Scala,在单次传递中具有O(n)时间和空间复杂度。
import collection.mutable.HashMap
def addUpToK(arr: Array[Int], k: Int): Option[Int] = {
val arrayHelper = new HashMap[Int,Int]()
def addUpToKHelper( i: Int): Option[Int] = {
if(i < arr.length){
if(arrayHelper contains k-arr(i) ){
Some(arr(i))
}else{
arrayHelper += (arr(i) -> (k-arr(i)) )
addUpToKHelper( i+1)
}
}else{
None
}
}
addUpToKHelper(0)
}
addUpToK(Array(10, 15, 3, 7), 17)
这是一个C实现 用于排序O(n2)时间和空间复杂度。 解决问题我们通过递归使用具有O(n)时间和空间复杂度的单次传递。 / *给定一个数字列表和一个数字k,返回天气列表中的任何两个数字加起来为k。例如,给定[10,15,3,7]和17的k,返回10 + 7是17奖励:你可以一次通过吗? * /
#include<stdio.h>
int rec(int i , int j ,int k , int n,int array[])
{
int sum;
for( i = 0 ; i<j ;)
{
sum = array[i] + array[j];
if( sum > k)
{
j--;
}else if( sum < k)
{
i++;
}else if( sum == k )
{
printf("Value equal to sum of array[%d] = %d and array[%d] = %d",i,array[i],j,array[j]);
return 1;//True
}
}
return 0;//False
}
int main()
{
int n ;
printf("Enter The Value of Number of Arrays = ");
scanf("%d",&n);
int array[n],i,j,k,x;
printf("Enter the Number Which you Want to search in addition of Two Number = ");
scanf("%d",&x);
printf("Enter The Value of Array \n");
for( i = 0 ; i <=n-1;i++)
{
printf("Array[%d] = ",i);
scanf("%d",&array[i]);
}
//Sorting of Array
for( i = 0 ; i <=n-1;i++)
{
for( j = 0 ; j <=n-i-1;j++)
{
if( array[j]>array[j+1])
{
//swapping of two using bitwise operator
array[j] = array[j]^array[j+1];
array[j+1] = array[j]^array[j+1];
array[j] = array[j]^array[j+1];
}
}
}
k = x ;
j = n-1;
rec(i,j,k,n,array);
return 0 ;
}
OUTPUT
Enter The Value of Number of Arrays = 4
Enter the Number Which you Want to search in addition of Two Number = 17
Enter The Value of Array
Array[0] = 10
Array[1] = 15
Array[2] = 3
Array[3] = 7
Value equal to sum of array[1] = 7 and array[2] = 10
Process returned 0 (0x0) execution time : 54.206 s
Press any key to continue.
这是python的实现
arr=[3,5,7,10]
k=17
flag=False
for i in range(0,len(arr)):
if k-arr[i] in arr:
flag=True
print( flag )
可以在阵列的一次传递中找到解决方案。初始化哈希集并开始迭代数组。如果在集合中找到数组中的当前元素,则返回true,否则将该元素的补集(x - arr [i])添加到集合中。如果数组的迭代结束而没有返回它意味着没有这样的对,其总和等于x,所以返回false。
public boolean containsPairWithSum(int[] a, int x) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i< a.length; i++) {
if(set.contains(a[i]))
return true;
set.add(x - a[i]);
}
return false;
}