Niuke net: somme des trois nombres

 

Table des matières

Méthode 1：Violence

Méthode 2：Double pointeur

---

Méthode 1：Violence

Le triple cycle devrait être quelque chose que tout le monde peut penser

Mais ça ne va pas

Et alors?,Utilise juste unO(nlogn)Ordre de complexité pour réduire la complexité,Comment baisser?？Les mêmes éléments seront réunis après le tri,On a juste rencontré le même saut direct.

Les codes sont les suivants:：

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> res;
        if(num.size()<3) return res;
        sort(num.begin(), num.end());
        for(int i=0;i<num.size()-2;++i){
            if(i&&num[i]==num[i-1]) continue;
            for(int j=i+1;j<num.size()-1;++j){
                if(j>i+1&&num[j]==num[j-1]) continue;
                for(int k=j+1;k<num.size();++k){
                    if(k>j+1&&num[k]==num[k-1]) continue;
                    if(num[i]+num[j]+num[k]==0){
                        res.push_back({num[i],num[j],num[k]});
                    }
                }
            }
        }
        return res;
    }
};

Méthode 2：Double pointeur

Nous pouvons réduire la complexité temporelle à O(n^2), D'abord, le tri. , Parce que ça nous permet de sauter les éléments répétitifs . Deuxièmement, il est également pratique pour nous d'utiliser le double pointeur .

Ensuite, le nombre dans le tableau est traité comme suit ：

1. Définissez le pointeur pour les deux derniers nombres , C'est - à - dire les pointeurs gauche et droit de la zone arrière

• Si la somme des trois nombres est égale à 0, Mettez trois nombres dans la réponse , Ensuite, mettez à jour les deux pointeurs à la position de l'élément non dupliqué
• Si plus de0, Déplacez le pointeur droit d'une position à gauche
• Si moins de0, Déplacez le pointeur gauche vers la droite

La condition de sortie est lorsque la position du pointeur gauche >= La position du pointeur droit

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> res;
        if(num.size()<3) return res;
        sort(num.begin(), num.end());
        for(int i=0;i<num.size();++i){
            if(i&&num[i]==num[i-1]) continue;
            int l=i+1,r=num.size()-1;
            while(l<r){
                if(num[i]+num[l]+num[r]==0){
                    res.push_back({num[i],num[l],num[r]});
                    while(l+1<r&&num[l]==num[l+1]) ++l;
                    while(r-1>l&&num[r]==num[r-1]) --r;
                    ++l,--r;
                }else if(num[l]+num[r]+num[i]>0){
                    --r;
                }else{
                    ++l;
                }
            }
        }
        return res;
    }
};