3Sum Closest : LeetCode

Problem

leetcode.com

与えられたInt型の配列numsの要素の内、３つ選んだ要素の和がtargetに最も近い値を見つける問題。

Solution

全列挙によるO(N³)の解法

配列の全ての３つの要素の和を算出し、その中から一番targetに近い値を見つける事で問題を解くことができる。 この時、配列の要素数をNとすると計算量はO(N³)となる。

いもす法によるO(N²)の解法

探索を始める前に配列をソートすることで計算量を小さくすることができる。 選択する３つの要素のインデックスをそれぞれleft, mid, rightとすると、leftを固定し、３つの要素の和に対してtargetより大きければrightを−１し、小さければmidを＋１する。これleftを0 ~ N - 2まですることで計算量O(N²)で解くことができる。

Source Code