N 개의 고유 정수 합계를 제로 Leetcode 솔루션 찾기

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Facebook Microsoft
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 87

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

Find N Unique Integers Sum up to Zero Leetcode Solution 문제는 정수를 제공합니다. 합계가 0 인 n 개의 고유 한 정수를 반환하도록 요청합니다. 따라서 질문은 이해하기 매우 간단합니다. 따라서 솔루션에 뛰어 들기 전에. 몇 가지 예를 살펴 보겠습니다.

N 개의 고유 정수 합계를 제로 Leetcode 솔루션 찾기

n = 5
[-7,-1,1,3,4]

설명 : 문제에 대한 여러 출력이있을 수 있습니다. 그러나 주어진 출력을 취합시다. 출력의 모든 정수는 고유합니다. 따라서 부과 된 조건과 주어진 모든 정수의 합은 0이됩니다. 따라서 두 조건이 모두 충족됩니다.

n = 3
[-1, 0, 1]

설명 : 주어진 출력은 모든 고유 한 정수를 가지며 그 합계도 0입니다. 따라서 출력은 부과 된 모든 조건을 충족합니다.

N 개의 고유 정수 합계를 제로 Leetcode 솔루션에 대한 접근 방식

문제에 대한 접근 방식은 대부분의 경우 패턴을 깨뜨리는 것입니다. 이러한 유형의 질문에는 항상 몇 가지 기본 패턴이 있습니다. 그래서 우리가 질문에 대한 패턴을 찾으려고 할 때마다. 항상 더 작은 n 값에 대한 답을 찾고 패턴을 찾으십시오. n = 1 인 경우 출력은 0이 될 수 있습니다. n = 2 인 경우 출력은 [-1, 1]이 될 수 있습니다. 마찬가지로 n = 3 인 경우 출력은 [-2, 0, 2]가 될 수 있고, n = 4 인 경우 출력은 [-3, -1, 1, 3]이 될 수 있습니다. 따라서 n의 값이 홀수이면 출력이 AP를 형성하는 패턴을 볼 수 있습니다. 중간 요소는 0입니다. n의 값이 짝수이면 (n + 1) / 2 요소는 1이됩니다. 따라서이 정보를 사용하여 공식을 고안 할 수 있습니다. 공식은 a [i] = 2 * i + 1-n 일 수 있습니다. 이제이 공식을 사용하여 정렬.

N 개의 고유 정수를 찾기위한 코드 합계가 XNUMX 인 Leetcode 솔루션

C ++ 코드

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

vector<int> sumZero(int n) {
    vector<int> v(n);
    for(int i=0;i<n;i++)
        v[i] = 2*i - n + 1;
    return v;
}

int main(){
    vector<int> output = sumZero(7);
    for(auto x: output)
        cout<<x<<" ";
}
-6 -4 -2 0 2 4 6

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    public static int[] sumZero(int n) {
        int[] v = new int[n];
        for(int i=0;i<n;i++)
            v[i]= 2*i - n + 1;
        return v;
    }
    
    public static void main(String[] args){
    	int[] output = sumZero(7);
    	for(int i=0;i<7;i++)
    		System.out.print(output[i]+" ");
    }
}
-6 -4 -2 0 2 4 6

복잡성 분석

시간 복잡성

의 위에), 단순히 배열을 채우고 각 요소를 O (1). 따라서 시간 복잡도는 선형입니다.

공간 복잡성

의 위에), 출력으로 반환되어야하는 배열을 생성하기 때문입니다.

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