3Sum Leetcode 솔루션  


난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 페이스북 서비스 구글 Microsoft 신탁 테슬라 VM웨어
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 두 포인터

문제 정책  

주어진 정렬 n 개의 정수 중 a + b + c = 0이되는 요소 a, b, c가 nums에 있습니까? XNUMX의 합을 제공하는 배열에서 모든 고유 한 XNUMX 중화를 찾습니다.
주의 사항 : 솔루션 세트에는 중복 된 XNUMX 색이 포함되어서는 안됩니다.

#1

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

설명 :3Sum Leetcode 솔루션

#2

[0]
[]

 

접근 방식 1 (Brute Force + 이진 검색)  

우리는 a + b + c = 0으로 고유 한 트리플렛을 찾아야합니다. 방정식 (a + b + c = 0)을 사용하여 a와 b의 값을 알고 있다고 가정 해 보겠습니다. c의 값을 찾을 수 있습니다.-( a + b).

가능한 모든 (a, b) 쌍을 취하면 2 개의 중첩 for 루프를 사용하여 a, b의 모든 쌍을 얻을 수 있습니다. 그 후 이진 검색을 사용하여 주어진 배열에 c =-(a + b)가 있는지 여부를 알 수 있습니다.
존재한다면 삼중 항 (a, b,-(a + b))은 가능한 삼중 항이 될 것입니다. 이런 식으로 a + b + c = 0으로 가능한 모든 트리플렛을 얻을 수 있지만 고유 한 트리플렛을 찾아야합니다.
이를 위해 우리는 고유 한 XNUMX 중을 얻기 위해 일부 데이터 구조 (즉, 집합)에 가능한 모든 XNUMX 중화를 삽입 할 수 있습니다.

3Sum Leetcode 솔루션 구현

C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> s;//to get unique triplets
        sort(nums.begin(),nums.end());
        int n=nums.size();
        vector<int> temp;
        temp.resize(3);
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
            {
                if(binary_search(nums.begin()+j+1,nums.end(),-nums[i]-nums[j])){
                     temp[0]=nums[i],temp[1]=nums[j],temp[2]=-nums[i]-nums[j];
                    sort(temp.begin(),temp.end());
                    //to get triplet in an order, will be easy to check if 
                    //duplicate exists or not
                    s.insert(temp);
                    }
            }
        vector<vector<int>> ans;
        for(auto triplet: s)
            ans.push_back(triplet);
        return ans;
}

void display_ans(vector<vector<int>> temp)
{
    for(auto triplet : temp) 
        cout<<triplet[0]<<" "<<triplet[1]<<" "<<triplet[2]<<"\n";
}

int main()
{
    vector<int> v{-1,0,1,2,-1,-4};
    display_ans(threeSum(v));
    return 0;
}
-1 -1 2 
-1 0 1

자바 프로그램

import java.util.*;
class Rextester{
    
  static boolean binary_search(int l,int r,int[]nums, int x)
    {
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(nums[mid]==x) return true;
            else if(nums[mid]>x) r=mid-1;
            else l=mid+1;
        }
        return false;
    }
    
    public static List<List<Integer>> threeSum(int[] nums) {
       
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int n=nums.length;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(binary_search(j+1,n-1,nums,-(nums[i]+nums[j])))
                {
                    List<Integer> t=new  ArrayList<Integer>();
                    t.add(nums[i]);
                    t.add(nums[j]);
                    t.add(-(nums[i]+nums[j]));
                    ans.add(t);
                }
                
                while(j+1<n && nums[j+1]==nums[j]) j++;
            }
            
            while(i+1<n && nums[i+1]==nums[i]) i++;
        }
        
        return ans;  
    }
    
  public static void main(String args[])
    {
       	int[] nums={-1,0,1,2,-1,-4};
        for(List<Integer> list:  threeSum(nums))
        {
            for(int x: list)
            System.out.print(x+ " ");
            System.out.println();
        }
    }
}
-1 -1 2 
-1 0 1

3Sum Leetcode 솔루션의 복잡성 분석

시간 복잡성

O (N * N * log (N)): 우리는 가능한 모든 (a, b) 쌍을 얻기 위해 두 개의 중첩 for 루프를 사용하고-(a + b)가 배열에 존재하는지 여부를 알기 위해 바이너리 검색을 사용합니다.

공간 복잡성 

의 위에): 우리는 독특한 세 쌍둥이를 얻기 위해 세트를 사용하고 있습니다.

접근 2 (두 포인터)  

동일한 작업을 수행하는 더 좋은 방법은 두 개의 포인터입니다. 기본 아이디어는 a를 선택한 다음 두 개의 포인터를 사용하여 a + b + c = 0이되는 b와 c를 찾는 것입니다.
b + c = a가되도록 두 포인터를 움직여야합니다.
까다로운 구현을 사용하면 고유 한 값을 얻기 위해 사용 된 set (
접근 방식의 세 쌍둥이 1)

3Sum Leetcode 솔루션 구현

C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
       vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n; i++)
        {
            int j=i+1,k=n-1;//two pointers
            while(j<n && j<k)
            {
                if(nums[j]+nums[k] == -nums[i])
                {
                    ans.push_back({nums[i],nums[j],nums[k]});
                    while(k!=0 && nums[k]==nums[k-1]) k--;//to avoid duplicates 
                    while(j!=n-1 && nums[j]==nums[j+1]) j++;
                    j++,k--;
                }
                else if(nums[j]+nums[k] > -nums[i]) 
                {
                    while(k!=0 && nums[k]==nums[k-1]) k--;
                    k--;
                }
                else
                {
                    while(j!=n-1 && nums[j]==nums[j+1]) j++;
                    j++;
                }
            }
            while(i!=n-1 && nums[i]==nums[i+1]) i++;
        }
        for(auto triplet : ans)
            sort(triplet.begin(),triplet.end());
        return ans;
}

void display_ans(vector<vector<int>> temp)
{
    for(auto triplet : temp) 
        cout<<triplet[0]<<" "<<triplet[1]<<" "<<triplet[2]<<"\n";
}

int main()
{
    vector<int> v{-1,0,1,2,-1,-4};
    display_ans(threeSum(v));
    return 0;
}
-1 -1 2 
-1 0 1

자바 프로그램

import java.util.*;

class Rextester{
    
  public static List<List<Integer>> threeSum(int[] nums) {
       
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int n=nums.length;
        
        for(int i=0;i<n;i++)
        {
            int p=i+1,q=n-1;
            while(p<q)
            {
                if(nums[p]+nums[q]==-nums[i])
                { //System.out.println(p+" "+q);
                    List<Integer> t=new ArrayList<Integer>();
                    t.add(nums[i]);
                    t.add(nums[p]);
                    t.add(nums[q]);
                 
                 ans.add(t);
                    
                    while(p+1<q &&  nums[p+1]==nums[p]) p++;
                    while(q-1>p &&  nums[q-1]==nums[q]) q--;
                    
                    p++; q--;
                }
                else if(nums[p]+nums[q] < -nums[i]) p++;
                else q--;
            }
            
            while(i+1<n && nums[i+1]==nums[i]) i++;
        }
        return ans;
    }
    
  public static void main(String args[])
    {
       	int[] nums={-1,0,1,2,-1,-4};
        for(List<Integer> list:  threeSum(nums))
        {
            for(int x: list)
            System.out.print(x+ " ");
            System.out.println();
        }
    }
}
-1 -1 2 
-1 0 1

3Sum Leetcode 솔루션의 복잡성 분석

시간 복잡성

O (N ^ 2): 우리는 a의 값을 얻기 위해 하나의 for 루프를 사용하고 있으며, a의 모든 값에 대해 O (N) 시간이 걸리는 두 포인터 접근 방식을 사용하여 쌍 b, c (예 : a + b + c = 0)를 찾습니다. 따라서 총 시간 복잡도는 O (N ^ 2) 정도입니다.

참조
주식 II Leetcode 솔루션을 사고 팔기 가장 좋은시기

공간 복잡성 

의 위에): 답을 저장하기 위해 벡터를 사용하고 있습니다.

1