给定一个数字列表和一个数字k,返回列表中的任何两个数字是否加起来为k

问题描述 投票:14回答:29

Google编程面试中提到了这个问题。我想到了两种相同的方法:

  1. 找到所有长度的子序列。这样做的同时计算两个元素的和,并检查它是否等于k。如果是的话,打印是,否则继续搜索。这是一种蛮力的方法。
  2. 以非递减顺序对数组进行排序。然后从右端开始遍历数组。假设我们有排序数组{3,5,7,10},我们希望总和为17.我们将从元素10开始,索引= 3,让我们用'j'表示索引。然后包括当前元素并计算required_sum = sum - current_element。之后,我们可以在数组[0-(j-1)]中执行二进制或三进制搜索,以查找是否存在其值等于required_sum的元素。如果我们找到这样一个元素,我们可以打破,因为我们找到了长度为2的子序列,其总和是给定的总和。如果我们没有找到任何这样的元素,那么减小j的索引并重复上述步骤以得到长度=长度为1的子阵列,即在这种情况下通过排除索引3处的元素。

在这里,我们认为数组可能有负整数和正整数。

你能提出比这更好的解决方案吗? DP解决方案可能吗?一种可以进一步降低时间复杂度的解决方案。

arrays algorithm time-complexity dynamic-programming subsequence
29个回答
16
投票

借助于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");

1
投票

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;
}

1
投票
    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。


1
投票

蟒蛇

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

1
投票

这是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

1
投票

我想出了两个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;
}

1
投票

Javascript解决方案:

function hasSumK(arr, k) {
    hashMap = {};
    for (let value of arr) {
        if (hashMap[value]) { return true;} else { hashMap[k - value] = true };
    }
    return false;
}

1
投票

这里有两个非常快速的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

1
投票

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)

0
投票

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);

0
投票

我的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;
 }

16
投票

这是一个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):

  1. 假设p1 = a [i]。然后,由于p1 + a [j] <p1 + p2,因此必须增加索引j。但是根据假设,我们知道[j + 1,n-1]不包含p2。矛盾。由此得出p1!= a [i]。
  2. j到j - 1类似。

由于在每次迭代时,[0,i-1]和[j + 1,n]不包含p1和p2,因此[i,j]确实包含p1和p2。最终a [i] = p1和a [j] = p2,算法返回true。


0
投票

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))

0
投票

使用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;
}

0
投票

这是一个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;
}

0
投票

我用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())
  }

0
投票

我在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))
}

0
投票

solution in javascript

这个函数需要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);

0
投票

我对每日编码问题的回答

# 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)

0
投票

以下是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

0
投票

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;
  }

0
投票

使用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);

4
投票

这是具有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;
}

4
投票

如果你想找对数,

pairs = [3,5,7,10]
k = 17
counter = 0

for i in pairs:
    if k - i in pairs:
        counter += 1

print(counter//2)

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))

1
投票

使用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)

1
投票

这是一个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.

1
投票

这是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 )

1
投票

可以在阵列的一次传递中找到解决方案。初始化哈希集并开始迭代数组。如果在集合中找到数组中的当前元素,则返回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;
 }
© www.soinside.com 2019 - 2024. All rights reserved.