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

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

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