Знайдзіце N унікальных цэлых лікаў, якія падводзяцца да нулявога рашэння Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка facebook Microsoft
масіў

Праблема Find N Unique Integers Sum Sum to Zero Leetcode Solution, забяспечвае нас цэлым лікам. Ён просіць нас вярнуць n унікальных цэлых лікаў, якія складаюць да 0. Такім чынам, пытанне даволі проста зразумець. Такім чынам, перш чым акунуцца ў раствор. Давайце разгледзім некалькі прыкладаў.

Знайдзіце 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]. Такім чынам, мы бачым заканамернасць, што на выхадзе фармуецца AP, калі значэнне n няцотнае. Сярэдні элемент роўны 0. Калі значэнне n роўнае, то элемент (n + 1) / 2 роўны 1. Такім чынам, выкарыстоўваючы гэтую інфармацыю, мы можам распрацаваць формулу. Формула можа быць [i] = 2 * i + 1-n. Цяпер мы проста выкарыстоўваем гэтую формулу для запаўнення n элементаў масіў.

Код, каб знайсці N унікальных цэлых лікаў Падвядзіце нулявое рашэнне 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

Код Java

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 (N), паколькі мы проста запаўняем масіў, і кожны элемент можа быць вылічаны O (1). Такім чынам, складанасць часу лінейная.

Касмічная складанасць

O (N), таму што мы ствараем масіў, які трэба вярнуць як вывад.