Solución LeetCode: suma de tres números

Dada una matriz de números que contiene n números enteros, determine si hay tres elementos A, B y C en números tales que a+b+c=0. Encuentre todos los triples cuya suma sea 0 y no se repitan.

Nota: Las respuestas no pueden contener tripletas duplicadas.

Entrada: nums =, [-1, 0, 1]]

De hecho, podemos convertir este problema en la suma de dos números en LeetCode. El método específico es el siguiente. siguiente:

p>

La premisa es que necesitamos ordenar la matriz.

Primero, la capa exterior se recorre primero como el primer número y el número objetivo se establece en -nums[first].

A continuación solo necesitamos dos punteros dobles, el segundo y el tercero, que apunten al primer +1 y al último número respectivamente, y los dos punteros se acercan al medio a medida que se recorren. Si nums[segundo]+nums[tercero]>objetivo, entonces el tercero se mueve hacia la izquierda; de lo contrario, el segundo se mueve hacia la izquierda. El segundo aumenta a medida que avanza el recorrido interior.

Debido a que hemos ordenado la matriz con anticipación, todavía no podemos encontrar la respuesta cuando el ciclo interno llega a segundo=tercero, por lo que nos saltamos el ciclo interno y vamos directamente al siguiente primero.

Análisis de Complejidad