NeetCode 150 [Two Pointers]:medium 2/3

NeetCodeのSolutionを書いていく

3Sum

問題概要

整数の配列numbersが与えられます。
合計値が0となる配列のi,j,k番目の値からなる3つの組み合わせを返しなさい。
組み合わせのi,j,kはそれぞれユニークです。

• 制約
  • 入力の配列数は 3 以上 1000 以下
  • 数値は -10^5 以上 10^5 以下

計算回数：O(n^2)
メモリ：O(1)
nはnumsの配列数

例

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

メモ

単純に2重ループで2つの数字を選んで、それに-1をかけた値を探せばOK？
答えを見ると、入力をsortして、2つ目、３つ目の値を前からと後ろからのポインタ移動で検索するのが効率的とのこと。
そうか、だからTowPointersか。

from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        retval = list()
        for i, ni in enumerate(nums):
            for j, nj in enumerate(nums[i + 1 : -1]):
                if -(ni + nj) in nums[i + 1 + j + 1 :]:
                    result = sorted((ni, nj, -(ni + nj)))
                    if result not in retval:
                        retval.append(result)
        return retval