Finden Sie in einem Array von Ganzzahlen zwei Zahlen, die sich zu einer bestimmten Zielzahl addieren. Die Funktion twoSum soll die Indizes der beiden Zahlen so zurückgeben, dass sie sich zum Ziel addieren, wobei index1 kleiner als index2 sein muss. Bitte beachten Sie, dass die von Ihnen zurückgegebenen
Antworten (sowohl index1 als auch index2) nicht nullbasiert sind.

Zum Beispiel:

Eingabe: Zahlen={2, 7, 11, 15}, Ziel=9
Ausgabe: index1=1, index2=2

Zwei Summen mit HashMap in Java

public class Solution {
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] result = new int[2];
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(numbers[i])) {
int index = map.get(numbers[i]);
result[0] = index+1 ;
result[1] = i+1;
break;
} else {
map.put(target - numbers[i], i);
}
}
return result;
}
}

Die Zeitkomplexität hängt von den Put- und Get-Operationen von HashMap ab, die normalerweise O (1) sind. Die zeitliche Komplexität dieser Lösung:O(n).

Zwei Summen mit einem sortierten Array

Dieses Problem ähnelt Two Sum. Um dieses Problem zu lösen, können wir zwei Punkte verwenden, um das Array von beiden Seiten zu scannen. Siehe
Java-Lösung unten:

public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == 0)
return null;
int i = 0;
int j = numbers.length - 1;
while (i < j) {
int x = numbers[i] + numbers[j];
if (x < target) {
++i;
} else if (x > target) {
j--;
} else {
return new int[] { i + 1, j + 1 };
}
}
return null;
}

Two Sum unter Verwendung von Datenstrukturdesign

Entwerfen und implementieren Sie eine TwoSum-Klasse. Es sollte die folgenden Operationen unterstützen:add und find.

add – Fügt die Nummer einer internen Datenstruktur hinzu.

find – Finden Sie heraus, ob es ein Zahlenpaar gibt, dessen Summe gleich dem Wert ist.
Zum Beispiel
add(1);
add(3);
add(5);
find(4) -> true
find(7) -> false

Da die gewünschte Klasse Add- und Get-Operationen benötigt, ist HashMap für
diesen Zweck eine gute Option.

public class TwoSum {
private HashMap<Integer, Integer> elements = new HashMap<Integer,
Integer>();
public void add(int number) {
if (elements.containsKey(number)) {
elements.put(number, elements.get(number) + 1);
} else {
elements.put(number, 1);
}
}
public boolean find(int value) {
for (Integer i : elements.keySet()) {
int target = value - i;
if (elements.containsKey(target)) {
if (i == target && elements.get(target) < 2) {
continue;
}
return true;
}
}
return false;
}
}

Dreisummenproblem in Java lösen

Gibt es bei einem gegebenen Array S von n ganzen Zahlen Elemente a, b, c in S, so dass a + b + c =0? Finden Sie alle eindeutigen Tripletts in dem Array, das die Summe Null ergibt.

Hinweis: Elemente in einem Triplett (a,b,c) müssen in nicht absteigender Reihenfolge sein. (dh a ≤ b ≤ c) Der Lösungssatz darf keine doppelten Tripletts enthalten.

Zum Beispiel

gegebenes Array S ={-1 0 1 2 -1 -4},
Ein Lösungssatz ist:
(-1, 0, 1)
(-1, -1, 2)

Eine bessere Lösung ist die Verwendung von zwei Zeigern anstelle von einem. Dies macht die Zeitkomplexität von O(n2ˆ).
Um Duplikate zu vermeiden, können wir sortierte Arrays nutzen, d. h. Zeiger um>1 verschieben, um dasselbe Element nur einmal zu verwenden.

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (num.length < 3)
return result;
// sort array
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
// //avoid duplicate solutions
if (i == 0 || num[i] > num[i - 1]) {
int negate = -num[i];
int start = i + 1;
int end = num.length - 1;
while (start < end) {
//case 1
if (num[start] + num[end] == negate) {
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(num[i]);
temp.add(num[start]);
temp.add(num[end]);
result.add(temp);
start++;
end--;
//avoid duplicate solutions
while (start < end && num[end] == num[end + 1])
end--;
while (start < end && num[start] == num[start - 1])
start++;
//case 2
} else if (num[start] + num[end] < negate) {
start++;
//case 3
} else {
end--;
}
}
}
}
return result;
}

Viersummenproblem in Java lösen

Gibt es bei einem gegebenen Array S von n ganzen Zahlen Elemente a, b, c und d in S, sodass a + b + c + d =Ziel? Finden Sie alle eindeutigen Quadrupel in dem Array, das die Summe des Ziels ergibt.

Hinweis: Elemente in einem Quadruplet (a,b,c,d) müssen in nicht absteigender Reihenfolge sein. (dh a ≤ b ≤ c ≤ d) Der Lösungssatz darf keine doppelten Quadrupel enthalten.

Zum Beispiel gegebenes Array S ={1 0 -1 0 -2 2} und Ziel =0.
Ein Lösungssatz ist:
(-1, 0, 0, 1)
(-2 , -1, 1, 2)
(-2, 0, 0, 2)

public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
Arrays.sort(num);
HashSet<ArrayList<Integer>> hashSet = new HashSet<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < num.length; i++) {
for (int j = i + 1; j < num.length; j++) {
int k = j + 1;
int l = num.length - 1;
while (k < l) {
int sum = num[i] + num[j] + num[k] + num[l];
if (sum > target) {
l--;
} else if (sum < target) {
k++;
} else if (sum == target) {
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(num[i]);
temp.add(num[j]);
temp.add(num[k]);
temp.add(num[l]);
if (!hashSet.contains(temp)) {
hashSet.add(temp);
result.add(temp);
}
k++;
l--;
}
}
}
}
return result;
}

Hier ist die hashCode-Methode von ArrayList. Es stellt sicher, dass, wenn alle Elemente der beiden Listen gleich sind, der Hash-Code der beiden Listen gleich ist. Da jedes Element in der ArrayList eine Ganzzahl ist, hat dieselbe Ganzzahl denselben Hashcode.
int hashCode = 1;
Iterator<E> i = list.iterator();
while (i.hasNext()) {
E obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}

Löse das Drei-Summen-Problem in Java

Gegeben sei ein Array S aus n ganzen Zahlen, suche drei ganze Zahlen in S, so dass die Summe einer gegebenen Zahl Ziel am nächsten kommt. Gibt die Summe der drei ganzen Zahlen zurück. Sie können davon ausgehen, dass jede Eingabe genau eine Lösung hätte. Beispiel:Gegebenes Array S =-1 2 1 -4 und Ziel =1. Die Summe, die dem Ziel am nächsten kommt, ist 2. (-1 + 2 + 1 =2)

Dieses Problem ist bei 2 Sum ähnlich. Diese Art von Problem kann mit einem ähnlichen Ansatz gelöst werden, d. h. zwei Zeiger von links und rechts.

public class Solution {
public int threeSumClosest(int[] num, int target) {
int min = Integer.MAX_VALUE;
int result = 0;
Arrays.sort(num);
for (int i = 0; i < num.length; i++) {
int j = i + 1;
int k = num.length - 1;
while (j < k) {
int sum = num[i] + num[j] + num[k];
int diff = Math.abs(sum - target);
if(diff == 0) return 0;
if (diff < min) {
min = diff;
result = sum;
}
if (sum <= target) {
j++;
} else {
k--;
}
}
}
return result;
}
}

Zeitkomplexität ist O(n2ˆ).