Βρείτε N μοναδικούς ακέραιους αθροιστές έως και μηδενική λύση Leetcode


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα Facebook Microsoft
Παράταξη

Το πρόβλημα Find N Unique Integers Sum έως Zero Leetcode Solution, μας παρέχει έναν ακέραιο. Μας ζητά να επιστρέψουμε n μοναδικούς ακέραιους αριθμούς έως και 0. Έτσι, η ερώτηση είναι αρκετά απλή στην κατανόηση. Λοιπόν, πριν βυθιστείτε στη λύση. Ας ρίξουμε μια ματιά σε μερικά παραδείγματα.

Βρείτε N μοναδικούς ακέραιους αθροιστές έως και μηδενική λύση Leetcode

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

Επεξήγηση: Λοιπόν, μπορεί να υπάρχουν πολλές έξοδοι στο πρόβλημα. Αλλά ας πάρουμε το δεδομένο αποτέλεσμα. Όλοι οι ακέραιοι αριθμοί στην έξοδο είναι μοναδικοί. Επομένως, η ικανοποίηση της επιβαλλόμενης συνθήκης και το άθροισμα όλων των δεδομένων ακέραιων είναι 0. Ως εκ τούτου, και οι δύο προϋποθέσεις πληρούνται.

n = 3
[-1, 0, 1]

Επεξήγηση: Η έξοδος που δίνεται έχει όλους τους μοναδικούς ακέραιους αριθμούς και το άθροισμά τους είναι επίσης 0. Έτσι, η έξοδος πληροί όλες τις επιβαλλόμενες προϋποθέσεις.

Προσέγγιση για εύρεση Ν μοναδικών ακεραίων Άθροισμα έως και μηδενική λύση 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ), αφού συμπληρώνουμε απλά τον πίνακα και κάθε στοιχείο μπορεί να υπολογιστεί σε Ο (1). Έτσι, η πολυπλοκότητα του χρόνου είναι γραμμική.

Διαστημική πολυπλοκότητα

ΕΠΙ), γιατί δημιουργούμε έναν πίνακα που πρέπει να επιστραφεί ως έξοδος.