Пронајдете N уникатно интегрално сумирање до решението за нулта код


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Facebook Мајкрософт
Низа

Проблемот Пронајдете N уникатни цели броеви до решението за нула лек код, ни обезбедува цел број. Бара од нас да вратиме n единствени цели броеви кои сумираат до 0. Значи, прашањето е прилично едноставно за разбирање. Значи, пред да се нурнете во растворот. Ајде да погледнеме неколку примери.

Пронајдете N уникатно интегрално сумирање до решението за нулта код

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

Објаснување: Па, може да има повеќе излези на проблемот. Но, да го земеме дадениот излез. Сите цели броеви на излезот се единствени. Така, задоволување на наметнатата состојба и збирот на сите дадени цели броеви е 0. Оттука, и двата услови се исполнети.

n = 3
[-1, 0, 1]

Објаснување: Дадениот излез ги има сите единствени цели броеви и нивниот збир е исто така 0. Така, излезот ги задоволува сите наметнати услови.

Пристап кон Најди ги N единствените цели броеви до решението за нулта кодна линија

Пристапот кон проблемите е во повеќето случаи кршење на моделот. Во овие типови на прашања секогаш има некои основни обрасци. Значи, секогаш кога ќе се обидеме да најдеме образец за прашање. Секогаш обидувајте се да го пронајдете одговорот за помали вредности на n, а потоа обидете се да ја пронајдете шемата. За n = 1, излезот може да биде 0. За n = 2, излезот може да биде [-1, 1]. Слично на n = 3, излезот може да биде [-2, 0, 2], за n = 4, излезот може да биде [-3, -1, 1, 3]. Значи, гледаме шема дека излезот формира АП каде што ако вредноста на n е непарна. Средниот елемент е 0. Ако вредноста на n е рамномерна, тогаш елементот (n + 1) / 2 е 1. Значи, користејќи ја оваа информација, можеме да смислиме формула. Формулата може да биде [i] = 2 * i + 1-n. Сега, ние едноставно ја користиме оваа формула за да ги пополниме n елементите на низа.

Код за да најдете N единствени цели броеви Збир до решение за нулта код

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

Анализа на сложеност

Временска комплексност

НА), бидејќи ние едноставно ја пополнуваме низата и секој елемент може да се пресмета во О (1). Така, временската сложеност е линеарна.

Комплексноста на просторот

НА), затоа што создаваме низа што треба да се врати како излез.