3 합계

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 Facebook 구글 Microsoft 신탁 Qualtrics 테슬라 VM웨어
배열 두 포인터조회수 67

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

3 Sum 문제에서 우리는 정렬 n 개의 정수의 수는 합계가 0 인 모든 고유 한 세 개의 삼중 선을 찾습니다.

입력:
숫자 = {-1, 0, 1, 2, -1, -4}
출력:
{-1, 0, 1}, {-1, 2, -1}

3 합계

3 합계 문제에 대한 순진한 접근 방식

문제를 해결하기위한 무차별 대입 접근 방식은 가능한 모든 트리플렛을 테스트하고 합계가 XNUMX 인 트리플렛을 선택하는 것입니다.
이는 세 개의 중첩 루프를 사용하여 달성 할 수 있습니다.

  1. 합계가 0 인 트리플렛을 저장하는 HashSet을 만듭니다.
  2. i = 0 ~ (n – 1)에 대해 루프를 실행합니다. 여기서 n은 배열의 요소 수입니다.
  3. j = (i + 1) ~ (n – 1)에 대해 중첩 루프를 실행합니다.
  4. k = (j + 1)에서 (n – 1)까지 루프를 하나 더 중첩합니다.
  5. 이 세 개의 루프는 고유 한 삼중 항 nums [i], nums [j] 및 nums [k]를 형성합니다. 삼중 항의 합은 (nums [i] + nums [j] + nums [k])입니다. 합이 XNUMX이면이 삼중 선 (i, j, k)을 삼중 선 HashSet에 추가합니다.
  6. 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 포인터 방법을 사용하는 것입니다.

  1. 오름차순으로 배열을 정렬합니다.
  2. 인덱스 i에있는 요소의 경우 앞에있는 요소의 두 요소와 함께 -nums [i] (nums [i]의 음수)의 합계를 만들어 삼중 항의 합계가 XNUMX이되도록합니다.
  3. 배열이 정렬되어 있기 때문에 필요한 sum (-nums [i])을 찾기 위해 여기에 두 개의 포인터 접근 방식을 적용 할 수 있습니다.
  4. 필요한 합을 합한 두 개의 요소가있는 경우 세 개의 요소 (요소 두 개와 nums [i])를 답 세트에 더합니다.
  5. 답안 세트를 인쇄하십시오.

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은 배열의 요소 수입니다.

참조

균열 시스템 설계 인터뷰
Translate »