Gegeben eine Liste von zahlen und eine Zahl k, gibt an, ob zwei beliebige zahlen aus der Liste hinzufügen von bis zu k

Diese Frage kann leicht gelöst werden mit Hilfe von set in O(N) Zeit und Raum Komplexität.Fügen Sie zunächst alle Elemente von array zu legen und dann Durchlaufen Sie jedes element von array und prüfen, ob K-ar[i] vorhanden ist oder nicht festgelegt.

Hier ist der code, der in java mit O(N) Komplexität :

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

Dies ist die java-Implementierung mit O(n) Zeitkomplexität und O(n) Speicherplatz. Die Idee ist eine HashMap enthalten wird ergänzt jedes array-element w.r.t target. Wenn die Ergänzung ist gefunden, wir haben 2 array-Elementen die Summe zum Ziel.

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

Python-Lösung:

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

Oder

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

Hier ist eine Umsetzung in C
Für das Sortieren O(n²) Zeit und Raum Komplexität.
Für die Lösung des Problems, das Wir verwenden
single-pass-mit O(n) Zeit und Raum Komplexität über Rekursion.

/* Eine Liste von zahlen und eine Zahl k , Rückkehr Wetter zwei beliebige zahlen aus der Liste hinzufügen von bis zu k.
Zum Beispiel, angegeben [10,15,3,7] und k 17 , return 10 + 7 ist 17
Bonus: Können Sie in einem Durchgang ? */

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

AUSGABE

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.

Die Lösung kann gefunden werden in nur einem Durchlauf das array. Initialisieren Sie einen hash-Set und starten Sie Durchlaufen das array. Wenn das aktuelle element im array gefunden wird, in der festgelegt wird true zurückgegeben, sonst fügen Sie das Komplement des Elements (x - arr[i]) der Satz. Wenn die iteration des Arrays beendet, ohne dass es bedeutet, dass es kein solches paar, deren Summe gleich x, also false zurück.

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

    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.

Hier ist Python. O(n). Müssen zum entfernen des aktuellen Elements, während looping, da die Liste möglicherweise nicht doppelte zahlen.

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

Javascript-Lösung:

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

Python-code:

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)

Mein C# - Implementierung:

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

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

Ich umgesetzt mit 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())
  }

Lösung in javascript

diese Funktion nimmt 2 Parameter und eine Schleife durch die Länge der Liste und innerhalb der Schleife gibt es eine weitere Schleife, die fügt eine Zahl zu anderen zahlen in der Liste und überprüfen Sie es die Summe wenn Ihr gleich k ist oder nicht

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

Hier ist der code in Python 3.7 mit O(N) Komplexität :

            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

und auch im besten Fall-code in Python 3.7 mit O(N^2) Komplexität :

            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

Mit vavr Bibliothek es getan werden kann, in ziemlich prägnanter Weise:

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