Two Sum Leetcode 솔루션-TutorialCup Two Sum Leetcode 솔루션

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

이 문제에서 우리는 두 개의 서로 다른 인덱스 쌍을 찾아야합니다. 분류 정렬 그들의 가치가 주어진 목표에 합산된다는 것을. 배열에 한 목표 합계에 더해지는 정수 쌍. 배열은 감소하지 않는 방법.

차례

예

Array = {1 , 2 , 3 , 4 , 5}
Target = 6

1 5

Array = {1 , 4 , 5 , 11 , 12}
Target = 9

2 3

접근 (Brute Force)

이 접근 방식은 간단합니다. 배열의 모든 쌍을 확인할 수 있으며 그 합계가 주어진 목표와 같으면 인덱스를 인쇄합니다. 이런 종류의 브 루트 포스 솔루션은 가능한 모든 쌍과 배열의 가능한 쌍 수를 확인해야합니다 = n * (n – 1) / 2. 따라서 최악의 경우이 접근 방식이 느릴 수 있습니다.

암호알고리즘

루프를 실행하여 배열에서 솔루션의 첫 번째 인덱스를 유지합니다.
첫 번째 정수마다 솔루션의 두 번째 인덱스를 유지하려면 다른 루프를 실행하십시오.
어느 시점에서든 두 인덱스 값의 합이 목표 값과 같으면
- 인덱스 인쇄

Two Sum Leetcode 솔루션 구현

C ++ 프로그램

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

vector <int> targetSum(vector <int> &a , int &target)
{
    int n = a.size();
    for(int i = 0 ; i < n - 1 ; i++)
        for(int j = i + 1 ; j < n ; j++)
        {
            if(a[i] + a[j] == target)
                return {i + 1 , j + 1};
        }
    return {};
}

int main()
{
    vector <int> a = {1 , 4 , 5 , 11 , 12};
    int target = 9;
    for(int &x : targetSum(a , target))
        cout << x << " ";
    cout << '\n';
}

자바 프로그램

class target_sum
{
    static int[] targetSum(int []a , int target)
    {
        for(int i = 0 ; i < a.length - 1 ; i++)
            for(int j = i + 1 ; j < a.length ; j++)
            {
                if(a[i] + a[j] == target)
                    return new int[]{i + 1 , j + 1};
            }
        return new int[]{-1 , -1};
    }


    public static void main(String args[])
    {
        int [] a = {1 , 4 , 5 , 11 , 12};
        int target = 9;

        for(int x : targetSum(a , target))
            System.out.print(x + " ");
    }
}

2 3

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

시간 복잡성

O (N * N), 여기서 N = 배열의 크기입니다. 가능한 쌍을 확인하고 총 쌍 수는 다음과 같습니다. N * (N – 1) / 2.

공간 복잡성

O (1). 변수에 대한 상수 공간 만 사용됩니다.

접근 (두 포인터)

암호알고리즘

주어진 배열은 정렬. 이것은 우리가 첫 번째 인덱스를 고정한 경우 목표를 충족하는 데 필요한 값이 다음을 사용하여 배열에서 미리 발견된다는 것을 알고 있기 때문에 특별한 경우입니다. 이진 검색.

비슷한 접근 방식을 사용할 수 있습니다. 두 포인터 : 왼쪽 및 권리, 처음에 먼저 그리고 지난 각각 배열의 요소. 그런 다음이 두 포인터 값의 합계를 대상과 비교할 수 있습니다. 값과 목표의 합이 같으면 만 해결책. 그래서 우리는이 인덱스 쌍을 반환합니다. 그렇지 않고 값의 합계가 적게 목표보다 포인터 중 하나를 증가 또는 감소시켜야합니다. 분명히, 우리는 연락해주세요 끝에서만 포인터. 따라서 우리는 왼쪽 (left) 포인터와 동일한 조건을 확인하십시오. 마찬가지로 값의 합계가 목표보다 크면 연락해주세요 바늘.

핀

구현 Two Sum Leetcode 솔루션

C ++ 프로그램

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

vector <int> targetSum(vector <int> &a , int &target)
{
    int left = 0 , right = int(a.size()) - 1 , tempSum;
    while(left < right)
    {
        tempSum = a[left] + a[right];
        if(tempSum == target)
            return {left + 1 , right + 1};
        if(tempSum > target)
            right--;
        else
            left++;
    }
    return {-1 , -1};
}

int main()
{
    vector <int> a = {1 , 4 , 5 , 11 , 12};
    int target = 9;
    for(int &x : targetSum(a , target))
        cout << x << " ";
    cout << '\n';
}

자바 프로그램

class target_sum
{
    static int[] targetSum(int []a , int target)
    {
        int left = 0 , right = a.length - 1 , tempSum;
        while(left < right)
        {
            tempSum = a[left] + a[right];
            if(tempSum == target)
                return new int[]{left + 1 , right + 1};
            if(tempSum > target)
                right--;
            else
                left++;
        }
        return new int[]{-1 , -1};
    }


    public static void main(String args[])
    {
        int [] a = {1 , 4 , 5 , 11 , 12};
        int target = 9;

        for(int x : targetSum(a , target))
            System.out.print(x + " ");
    }
}

2 3

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

시간 복잡성

의 위에), 최악의 경우에도 배열의 모든 요소를 한 번만 방문합니다.

공간 복잡성

O (1). 변수에 상수 공간을 사용합니다.