시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
3 Sum 문제에서 우리는 정렬 n 개의 정수의 수는 합계가 0 인 모든 고유 한 세 개의 삼중 선을 찾습니다.
차례
예
입력:
숫자 = {-1, 0, 1, 2, -1, -4}
출력:
{-1, 0, 1}, {-1, 2, -1}
3 합계 문제에 대한 순진한 접근 방식
문제를 해결하기위한 무차별 대입 접근 방식은 가능한 모든 트리플렛을 테스트하고 합계가 XNUMX 인 트리플렛을 선택하는 것입니다.
이는 세 개의 중첩 루프를 사용하여 달성 할 수 있습니다.
- 합계가 0 인 트리플렛을 저장하는 HashSet을 만듭니다.
- i = 0 ~ (n – 1)에 대해 루프를 실행합니다. 여기서 n은 배열의 요소 수입니다.
- j = (i + 1) ~ (n – 1)에 대해 중첩 루프를 실행합니다.
- k = (j + 1)에서 (n – 1)까지 루프를 하나 더 중첩합니다.
- 이 세 개의 루프는 고유 한 삼중 항 nums [i], nums [j] 및 nums [k]를 형성합니다. 삼중 항의 합은 (nums [i] + nums [j] + nums [k])입니다. 합이 XNUMX이면이 삼중 선 (i, j, k)을 삼중 선 HashSet에 추가합니다.
- XNUMX으로 합산되는 모든 트리플렛이 HashSet에 있으므로 HashSet의 내용을 인쇄하십시오.
3 합계에 대한 JAVA 코드
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 합계에 대한 C ++ 코드
#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
복잡성 분석
시간 복잡성 = 의 위에3)
공간 복잡성 = O (1)
여기서 n은 배열의 요소 수입니다.
3 Sum 문제에 대한 최적의 접근 방식
더 나은 방법은 3 포인터 방법을 사용하는 것입니다.
- 오름차순으로 배열을 정렬합니다.
- 인덱스 i에있는 요소의 경우 앞에있는 요소의 두 요소와 함께 -nums [i] (nums [i]의 음수)의 합계를 만들어 삼중 항의 합계가 XNUMX이되도록합니다.
- 배열이 정렬되어 있기 때문에 필요한 sum (-nums [i])을 찾기 위해 여기에 두 개의 포인터 접근 방식을 적용 할 수 있습니다.
- 필요한 합을 합한 두 개의 요소가있는 경우 세 개의 요소 (요소 두 개와 nums [i])를 답 세트에 더합니다.
- 답안 세트를 인쇄하십시오.
3 합계에 대한 JAVA 코드
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 합계에 대한 C ++ 코드
#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
복잡성 분석
시간 복잡성 = 의 위에2)
공간 복잡성 = O (1)
여기서 n은 배열의 요소 수입니다.
