マツシタのお勉強

3Sum Closest : LeetCode

Problem

leetcode.com

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

Solution

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

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

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

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

Source Code