Учитывая список чисел и число k, верните, будут ли любые два числа из списка складываться до k

Ответ 1

Этот вопрос можно легко решить с помощью набора в 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");

Ответ 2

Вот реализация 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.). Предположим, что a[0,n] содержит p1 и p2. В случае, если это не так, алгоритм, очевидно, является правильным.

Базовый случай (i = 0, j = n): a[0,-1] не содержит p1, а a[n,n+1] не содержит p2.

Гипотеза: a[0,i-1] не содержит a[i], а a[j+1,n] не содержит p2.

Шаг (от i до i + 1 или от j до j - 1):

1. Предположим p1 = a[i]. Затем, начиная с p1 + a[j] < p1 + p2, индекс j должен быть увеличен. Но из этой гипотезы мы знаем, что a[j+1,n-1] не содержит p2. Противоречие. Отсюда следует, что p1 != a[i].
2. от j до j - 1 аналогично.

Поскольку каждая итерация, a[0,i-1] и a[j+1,n], не содержит p1, а p2, a[i,j] содержит p1 и p2. В конце концов, a[i] = p1 и a[j] = p2 и алгоритм возвращает true.

Ответ 3

если вы хотите найти количество пар,

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

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

print(counter//2)

Ответ 4

Это реализация java с O (n) временной сложностью и O (n). Идея состоит в том, что HashMap будет содержать дополнения для каждого элемента массива. Если дополнение найдено, у нас есть 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;
}

Ответ 5

Python Решение:

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

Ответ 6

Решение Javascript:

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

Ответ 7

Использование 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)

Ответ 8

Вот реализация C
Для сортировки O (n ²) сложности времени и пространства.
Для решения проблемы Мы используем один проход с O (n) временем и пространственной сложностью через Recursion.
/* Учитывая список чисел и число k, возвратите погоду, любые два числа из списка складываются до k. Например, учитывая [10,15,3,7] и k из 17, возврат 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 ;
}

ВЫХОД

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.

Ответ 9

Вот реализация 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 )

Ответ 10

Решение можно найти всего за один проход массива. Инициализируйте хэш Установите и начните итерацию массива. Если текущий элемент в массиве найден в наборе, тогда верните 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;
 }

Ответ 11

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

Ответ 12

питон

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

Ответ 13

Здесь 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

Ответ 14

Я предложил два решения в 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;
}

Ответ 15

Код 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)

Ответ 16

    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.

Ответ 17

Решение С#:

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

Ответ 18

Моя реализация С#:

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

Ответ 19

Реализация Python: код будет выполняться в O (N) сложности с использованием словаря. Мы бы сохранили (требуемый_отход - текущий_вход) в качестве ключа в словаре. И тогда мы проверим, существует ли число в словаре или нет. Поиск по словарю имеет среднюю сложность как 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))

Ответ 20

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

Ответ 21

Вот решение 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;
}

Ответ 22

Я реализовал с помощью 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())
  }

Ответ 23

Я пробовал решение в 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))
}

Ответ 24

Здесь две очень быстрые реализации 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 → ca=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

Ответ 25

Решение в 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);

Ответ 26

Мой ответ на ежедневную проблему кодирования

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

Ответ 27

проверить это - https://www.geeksforgeeks.org/given-an-array-a-and-a-number-x-check-for-pair-in-a-with-sum-as-x/

В методе 2 это реализуется в O (n) времени и пространства сложности.

HashSet реализован с использованием HashTable. Поэтому метод .contains занимает постоянное время O (1), что делает общую временную сложность программы O (n).

Ответ 28

Вот код в 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

Ответ 29

Решение 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;
  }

Ответ 30

С помощью библиотеки 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);