3 Cəmi problemində bir array n ədəd ədədi, 0-a yekun vuran bütün unikal üçlükləri tapın.
Mündəricat
misal
Input:
saylar = {-1, 0, 1, 2, -1, -4}
Çıxış:
{-1, 0, 1}, {-1, 2, -1}
3 Sum problemi üçün sadəlövh yanaşma
Problemi həll etmək üçün Brute force yanaşması bütün mümkün üçləri sınamaq və sıfıra qədər olanları seçməkdir.
Buna üç iç içə döngə istifadə edərək nail olmaq olar.
- 0 məbləğində üçəmləri saxlamaq üçün bir HashSet yaradın.
- İ = 0 ilə (n - 1) arasında bir döngə çalıştırın, burada n sıradakı elementlərin sayıdır.
- J = (i + 1) ilə (n - 1) arasında bir iç içə döngə işlədin.
- K = (j + 1) ilə (n - 1) arasında bir döngə daha yerləşdirin.
- Bu üç döngə nums [i], nums [j] və nums [k] misilsiz bir üçlüyü əmələ gətirir. Üçlüyün cəmi (nums [i] + nums [j] + nums [k]). Cəmi sıfırsa, bu üçlüyü (i, j, k) HashSet üçlülərinə əlavə edin.
- Sıfıra yekunlaşdıran bütün üçüzlər HashSet-də mövcuddur, ona görə HashSet-in məzmunu çap olunur.
3 Sum üçün JAVA Kodu
public class ThreeSum {
private static void printUniqueTriplets(int[] nums) {
int n = nums.length;
// Created a set of triplets to avoid duplicates
HashSet<Triplet> triplets = new HashSet<>();
// Use 3 nested loop to check all the possible combinations
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
// If this triplet sums to zero, add it in the set
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
triplets.add(new Triplet(nums[i], nums[j], nums[k]));
}
}
}
}
// Print the unique triplets
for (Triplet triplet : triplets) {
System.out.println(triplet.ele[0] + " " + triplet.ele[1] + " "
+ triplet.ele[2]);
}
}
public static void main(String[] args) {
// Example
int nums[] = new int[]{-1, 0, 1, 2, -1, -4};
printUniqueTriplets(nums);
}
// class representing a triplet
static class Triplet {
int ele[];
public Triplet(int first, int second, int third) {
ele = new int[3];
ele[0] = first;
ele[1] = second;
ele[2] = third;
// Store the triplets in ascending order, so that this could be used
// in checking duplicates
Arrays.sort(ele);
}
// Two triplets are equal if elements in them are same
@Override
public boolean equals(Object o) {
Triplet t = (Triplet) o;
return (Arrays.compare(ele, t.ele) == 0);
}
@Override
public int hashCode() {
return Arrays.hashCode(ele);
}
}
}
-1 -1 2 -1 0 1
3 məbləğ üçün C ++ kodu
#include <bits/stdc++.h>
using namespace std;
// structure representing a triplet
struct Triplet {
int ele[3];
bool operator==(const Triplet& t) const {
return (this->ele[0] == t.ele[0] && this->ele[1] == t.ele[1] && this->ele[2] == t.ele[2]);
}
};
// custom hash function for triplet
class MyHash {
public:
size_t operator()(const Triplet& t) const {
return t.ele[0] + 10 * t.ele[1] + 100 * t.ele[2];
}
};
void printUniqueTriplets(int *nums, int n) {
// Created a set of triplets to avoid duplicates
unordered_set<Triplet, MyHash> triplets;
// Use 3 nested loop to check all the possible combinations
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int sum = nums[i] + nums[j] + nums[k];
// If this triplet sums to zero, add it in the set
if (sum == 0) {
Triplet triplet;
int e[3];
e[0] = nums[i];
e[1] = nums[j];
e[2] = nums[k];
sort(e, e + 3);
triplet.ele[0] = e[0];
triplet.ele[1] = e[1];
triplet.ele[2] = e[2];
triplets.insert(triplet);
}
}
}
}
// Print the unique triplets
for (auto itr = triplets.begin(); itr != triplets.end(); itr++) {
cout<<itr->ele[0]<<" "<<itr->ele[1]<<" "<<itr->ele[2]<<endl;
}
}
int main() {
// Example
int nums[] = {-1, 0, 1, 2, -1, -4};
printUniqueTriplets(nums, sizeof(nums) / sizeof(nums[0]));
}
-1 -1 2 -1 0 1
Mürəkkəblik təhlili
Zaman Mürəkkəbliyi = O (n)3)
Kosmik Mürəkkəblik = O (1)
burada n - massivdəki elementlərin sayı.
3 Sum problemi üçün optimal yanaşma
Daha yaxşı yanaşma 3 göstərici metodundan istifadə etməkdir.
- Dizini artan qaydada çeşidləyin.
- İ indeksindəki bir element üçün, üçlü sıfıra çatması üçün, qarşıdakı elementlərdən iki elementlə -nums [i] (numların mənfi [i]) cəmini düzəltməyə çalışın.
- Dizinin sıralandığı üçün tələb olunan cəmi (-nums [i]) tapmaq üçün iki göstərici yanaşması tətbiq olunur.
- Tələb olunan cəmi toplayan iki element varsa, cavab dəstinə üçlü (iki element və saylar [i]) əlavə edin.
- Cavab dəstini çap edin.
3 Sum üçün JAVA Kodu
import java.util.Arrays;
import java.util.HashSet;
public class ThreeSum {
private static void printUniqueTriplets(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
HashSet<Triplet> triplets = new HashSet<>();
for (int i = 0; i < n; i++) {
int req = -nums[i];
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == req) {
triplets.add(new Triplet(nums[i], nums[left], nums[right]));
// Check for more triplets
left++;
right--;
} else if (sum < req) {
left++;
} else {
right--;
}
}
}
// Print the unique triplets
for (Triplet triplet : triplets) {
System.out.println(triplet.ele[0] + " " + triplet.ele[1] + " "
+ triplet.ele[2]);
}
}
public static void main(String[] args) {
int nums[] = new int[]{-1, 0, 1, 2, -1, -4};
printUniqueTriplets(nums);
}
// class representing a triplet
static class Triplet {
int ele[];
public Triplet(int first, int second, int third) {
ele = new int[3];
ele[0] = first;
ele[1] = second;
ele[2] = third;
// Store the triplets in ascending order, so that this could be used
// in checking duplicates
Arrays.sort(ele);
}
// Two triplets are equal if elements in them are same
@Override
public boolean equals(Object o) {
Triplet t = (Triplet) o;
return (Arrays.compare(ele, t.ele) == 0);
}
@Override
public int hashCode() {
return Arrays.hashCode(ele);
}
}
}
-1 -1 2 -1 0 1
3 məbləğ üçün C ++ kodu
#include <bits/stdc++.h>
using namespace std;
// structure representing a triplet
struct Triplet {
int ele[3];
bool operator==(const Triplet& t) const {
return (this->ele[0] == t.ele[0] && this->ele[1] == t.ele[1] && this->ele[2] == t.ele[2]);
}
};
// custom hash function for triplet
class MyHash {
public:
size_t operator()(const Triplet& t) const {
return t.ele[0] + 10 * t.ele[1] + 100 * t.ele[2];
}
};
void printUniqueTriplets(int *nums, int n) {
sort(nums, nums + n);
// Created a set of triplets to avoid duplicates
unordered_set<Triplet, MyHash> triplets;
for (int i = 0; i < n; i++) {
int req = -nums[i];
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == req) {
// Add this triplet to the set
Triplet triplet;
int e[3];
e[0] = nums[i];
e[1] = nums[left];
e[2] = nums[right];
sort(e, e + 3);
triplet.ele[0] = e[0];
triplet.ele[1] = e[1];
triplet.ele[2] = e[2];
triplets.insert(triplet);
// Check for more triplets
left++;
right--;
} else if (sum < req) {
left++;
} else {
right--;
}
}
}
// Print the unique triplets
for (auto itr = triplets.begin(); itr != triplets.end(); itr++) {
cout<<itr->ele[0]<<" "<<itr->ele[1]<<" "<<itr->ele[2]<<endl;
}
}
int main() {
// Example
int nums[] = {-1, 0, 1, 2, -1, -4};
printUniqueTriplets(nums, sizeof(nums) / sizeof(nums[0]));
}
-1 -1 2 -1 0 1
Mürəkkəblik təhlili
Zaman Mürəkkəbliyi = O (n)2)
Kosmik Mürəkkəblik = O (1)
burada n - massivdəki elementlərin sayı.
