a + b + c = sum과 같은 다른 세 배열에서 세 요소 찾기

난이도 중급
자주 묻는 질문 아마존 데이터 브릭 지시 JP 모건 택시4슈어 Twilio 조호 (Zoho)
배열 해시 해싱조회수 70

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

Three Sum은 면접관들이 좋아하는 문제입니다. 제가 개인적으로 질문 한 문제입니다. 아마존 회견. 따라서 더 이상 시간을 낭비하지 않고 문제를 해결하겠습니다. 양수와 음수가 모두있는 배열입니다. 합이 XNUMX이되는 XNUMX 개의 숫자를 수정하여 임의의 정수로 합하거나 a + b + c = 합계가되도록 다른 세 배열에서 XNUMX 개 요소를 찾을 수 있습니다.

입력

[-2,0,1,1,2]

산출

[[-2,0,2], [-2,1,1]]

그것을 해결하는 방법?

독자들에게 더 큰 고통이되기 전에. 같은 것을 보여주는 작은 의사 코드를 살펴 보겠습니다. 단계별 :

  • 첫째로 종류 숫자들.
  • 정렬은 숫자의 크기에 따라 숫자에 액세스하는 데 도움이됩니다.
  • 둘째, 배열에서 요소를 선택합니다.
  • 세 번째로 첫 번째 요소를 합하면 XNUMX이되는 두 요소를 선택합니다.
  • Deja Vu를 가지고 있다면 힌트를 떨어 뜨릴 수 있습니다.
  • 또한 SUM 문제.
  • 첫 번째 요소를 수정하면 다른 두 요소를 찾기 위해 배열을 실행합니다.
  • 우리는 두 가지 목적을 가지고 있습니다.
  • 두 끝의 합이 원하는 것보다 클 때마다 끝 값을 감소시킵니다.
  • 두 끝의 합이 원하는 것보다 적을 때마다 시작 값을 증가시킵니다.
  • 합계가 0에 도달하면 요소를 기록합니다.
  • 마지막으로 요소는 반복되지 않도록 집합의 ArrayList에 추가됩니다.

Three Sum에 대한 Java 코드

class Solution 
{
    public List<List<Integer>> threeSum(int[] nums) 
    {
        Arrays.sort(nums);
        if(nums.length<3)
            return new ArrayList<>();
        Set<List<Integer>>lisa=new HashSet<>();
        for(int i=0;i<nums.length;i++)
        {
            int start=i+1;
            int end=nums.length-1;
            while(end>start)
            {
                int sum=nums[i]+nums[start]+nums[end];
                if(sum==0)
                {
                    List<Integer>cur=new ArrayList<Integer>();
                    cur.add(nums[i]);
                    cur.add(nums[start]);
                    cur.add(nums[end]);
                    lisa.add(cur);
                    end--;
                    start++;
                }
                else if(sum>0)
                    end--;
                else if(sum<0)
                    start++;
            }
        }
        return new ArrayList<>(lisa);
    }
}

Three Sum에 대한 C ++ 코드

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(),nums.end());
        vector<vector<int>>ans;
        set<vector<int>>lisa;
        for(int i=0;i<nums.size();i++)
        {
            int start=i+1;
            int end=nums.size()-1;
            while(end>start)
            {
                int sum=nums[i]+nums[start]+nums[end];
                if(sum==0)
                {
                    lisa.insert({nums[i],nums[start],nums[end]}); 
                    end--;
                    start++;
                }
                else if(sum>0)
                    end--;
                else if(sum<0)
                    start++;
            }
        }
        for(auto x:lisa)
        {
            ans.push_back(x);
        }
        return ans;
    }
};

복잡성 분석

시간 복잡도 = O (n ^ 2)

공간 복잡성 = O (1)

어떻게?

XNUMX 합에 대한 시간 복잡도 분석

  • 첫째, 수정할 수있는 첫 번째 요소를 찾으면 외부 루프를 실행합니다.
  • 내부 루프.
  • 첫 번째 요소를받습니다.
  • 끝에서 두 번째 요소를 가져옵니다.
  • 더 나쁜 경우에는 첫 번째 요소에서 마지막 요소로 이동하기 시작할 수 있습니다.
  • 이것은 O (n ^ 2)의 시간 복잡도로 이어집니다.

XNUMX 합에 대한 공간 복잡성 분석

  • 추적을 위해 몇 가지 변수 만 사용합니다.
  • 따라서 공간 복잡성이 O (1)

작은 조정

Three Sum 문제의 저장 단위를 변경하면 어떨까요? 놀란!?

별거 아니야. 우리는 단일 배열이 아닌 XNUMX 개의 다른 배열을 사용합니다. 당신이 여전히 그것을 얻지 못한 경우. 샘플 테스트 케이스를 보여 드리겠습니다.

입력

어레이 1 = {1, 2, 3, 4, 5}

어레이 2 = {2, 3, 6, 1, 2}

배열 3 = {3, 2, 4, 5, -6}

산출

다음은 가능한 세 쌍둥이를 강조하는 이미지입니다.

세 합계

문제에 접근하는 방법

  • 첫째, 우리는 두 배열에서 합의 가능한 모든 조합을 생성하려고합니다.
  • 이를 위해 우리는 두 개의 루프를 실행합니다.
  • 반복을 피하기 위해 이러한 모든 조합을 세트에 저장합니다.
  • 합계의 -ve 값이 세 번째 배열에서 사용 가능한지 확인합니다.
  • 그렇다면 예를 반환합니다.
  • 마지막으로 모든 배열을 반복 한 후에도 0이되지 않으면 false를 반환합니다.

Three Sum에 대한 Java 코드

public class Main
{
    public static boolean Three(int a1[],int a2[],int a3[])
    {
        Set<Integer>store=new HashSet<Integer>();
        Set<ArrayList<Integer>>lisa=new HashSet<>();
        for(int i=0;i<a2.length;i++)
        {
            for(int j=0;j<a3.length;j++)
                store.add(a2[i]+a3[j]);
        }
        for(int i=0;i<a1.length;i++)
        {
            if(store.contains(-a1[i]))
            {
                return true;
            }
        }
        return false;
    }
    public static void main (String[] args) 
    { 
        int a1[] = { 1 , 2 , 3 , 4 , 5 }; 
        int a2[] = { -2 , 3 , 6 , 1 , 2 }; 
        int a3[] = { 3 , 2 , -4 , 5 , -6 }; 
          
        int n1 = a1.length; 
        int n2 = a2.length; 
        int n3 = a3.length; 
          
        System.out.println(Three(a1, a2, a3));
    } 
}

Three Sum에 대한 C ++ 코드

bool Three(int a1[],int a2[],int a3[])
    {
    int n1 = sizeof(a1) / sizeof(a1[0]); 
    int n2 = sizeof(a2) / sizeof(a2[0]); 
    int n3 = sizeof(a3) / sizeof(a3[0]); 
    set<int>store;
    for(int i=0;i<n2;i++)
    {
        for(int j=0;j<n3;j++)
            store.insert(a2[i]+a3[j]);
    }
    for(int i=0;i<n1;i++)
    {
        if(store.find(-a1[i])!=store.end())
        {
            return true;
        }
    }
    return false;
}
int main() 
{ 
    int a1[] = { 1 , 2 , 3 , 4 , 5 }; 
    int a2[] = { 2 , 3 , 6 , 1 , 2 }; 
    int a3[] = { 3 , 2 , 4 , 5 , 6 }; 
    cout<<Three(a1, a2, a3);
  
    return 0; 
}

복잡성 분석

시간 복잡도 = O (n ^ 2)

어떻게?

  • 두 번째 배열에서 요소를 찾기 위해 외부 루프를 실행합니다.
  • 내부 루프에서 세 번째 배열의 요소를 두 번째 배열 요소에 추가합니다.
  • 지금까지 발생한 시간 복잡도는 O (n ^ 2)입니다.
  • 다음 루프는 첫 번째 배열의 요소를 확인합니다.
  • 이 루프의 시간 복잡도 = O (1)
  • 지금까지의 최종 복잡도 = O (n ^ 2) + O (1) = O (n ^ 2)

공간 복잡성 = O (n)

어떻게?

  • 모든 요소를 ​​저장하기 위해 세트를 사용합니다.
  • 이것은 O (n)의 시간 복잡성으로 이어집니다.
균열 시스템 설계 인터뷰
Translate »