Comment résoudre le problème de la somme de trois nombres en PHP

Étant donné un tableau nums contenant n entiers, déterminez s'il y a trois éléments a, b, c dans des nombres tels que a+b+c=0 ? Que devons-nous faire lorsque nous rencontrons ce genre de problème ? Aujourd’hui, je vais vous expliquer cela.

Donnez Vous avez un tableau nums contenant n entiers, déterminez s'il y a trois éléments a, b, c en nombres tels que a + b + c = 0 ? Veuillez trouver tous les triples qui remplissent les conditions et qui ne se répètent pas.

Remarque : les triples répétés ne sont pas autorisés dans la réponse.

Exemple :

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：[
 [-1, 0, 1],
 [-1, -1, 2]]

Idée de résolution de problèmes 1

Méthode d'énumération violente, à trois niveaux pour + si le jugement suffit, pour que l'offre soit fait pendant l’entretien Devenir celui de quelqu’un d’autre. Si vous n’écrivez plus de code, celui-ci expirera facilement si la quantité de données est importante.

Idée de résolution de problèmes 2

Vous pouvez d'abord fixer une valeur, puis utiliser une méthode à double pointeur pour trouver les deux dernières valeurs, optimisant ainsi la complexité temporelle totale à O (n^2).

Pendant le processus de mise en œuvre, une attention particulière doit être portée à l'optimisation et à la déduplication.

Nous trions d'abord le tableau d'origine, afin que les valeurs en double puissent être rassemblées pour faciliter la déduplication.

Lors de la détermination du premier élément, s'il est déjà supérieur à 0, vous pouvez directement sortir de la boucle, car les nombres suivants sont tous supérieurs à lui. Par exemple, [1, 2, 3, 4], i = 0, nums[i] > 0, il est impossible de produire une situation juridique, alors rompez simplement.

Lors de la détermination du premier élément, s'il s'avère qu'il est identique à la valeur qui le précède, sautez ce tour. Par exemple, [-1, -1, 0, 1], après le premier tour, {-1, 0, 1} a été sélectionné, maintenant i = 1, nums[i] == nums[i - 1], Pour éviter les doublons, continuez directement.

Ensuite, utilisez des pointeurs doubles, les points gauches vers i + 1 et les points droits pour compter ($nums) - 1. Portez des jugements un par un et veillez à supprimer les doublons. C'est un peu comme fixer une valeur, puis utiliser deux pointeurs pour trouver la somme des deux nombres.

class Solution {
    /** * @param Integer[] $nums * @return Integer[][] */
    function threeSum($nums) {
        $result = [];
        $count = count($nums);
        if ($nums === null || count($nums) <= 2) return $result;
        sort($nums); // O(nlogn)
        for ($i = 0; $i < $count - 2; $i++) { // O(n^2)
            if ($nums[$i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
            if ($i > 0 && $nums[$i] === $nums[$i - 1]) continue; // 去掉重复情况
            $target = -$nums[$i];
            $left = $i + 1;
            $right = $count - 1;
            while ($left < $right) {
                if ($nums[$left] + $nums[$right] === $target) {
                    $result[] = [$nums[$i], $nums[$left], $nums[$right]];
                    // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                    $left++;
                    $right--; // 首先无论如何先要进行加减操作
                    while ($left < $right && $nums[$left] === $nums[$left - 1]) $left++;
                    while ($left < $right && $nums[$right] === $nums[$right + 1]) $right--;
                } else if ($nums[$left] + $nums[$right] < $target) {
                    $left++;
                } else {  // $nums[$left] + $nums[$right] > $target
                    $right--;
                }
            }
        }
        return $result;
    }}

Apprentissage recommandé : tutoriel vidéo php

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!