LeetCodeって？
LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。
2022年12月現在2,000問を超える問題が登録されています。
各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。
正誤判定は自動で行われます。
使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。
私はPython3で解いています。
Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量 [ 増井 敏克 ]
問題
タイトル：16. 3Sum Closest
難易度：Medium
内容：
整数が入ったリスト nums と整数 target が与えられる。
nums の中から足すと target の値に最も近くなる3つの値の組み合わせを抽出しその和を返す。
例：
nums = [-1,2,1,-4], target = 1 返り値: 2 ※最も1に近い組み合わせは -1 +2 +1 = 2
nums = [0,0,0], target = 1 返り値: 0
回答
前回の 3Sum と似ていますので同様に 2pointer を使って解いていきます
何はともあれソートします。
また返り値と、これまで見つかった組み合わせの中で最も和が target に近かったものとの差分の変数を初期化します。
nums_sorted = sorted(nums) # numsをソート
ans = min_dif = 1e10 # 返り値と暫定最もtargetに近い値を格納する変数の初期化2 pointer
3つの値を x, y, z とし x を更新しながら2 pointer を行っていきます。
まず x は最小の値、y はその次の値、zを最大の値とします。
x + y + z が target より小さい場合は y を右に移動、大きい場合は z を左に移動していき、最も target に近かった値を min_dif に代入します。
y, z が移動できなくなったら今度は x を1つ右に移動して再度 2pointer を行います。
これにより全てのありうる組み合わせを探索し target に最も近いものを探します。
なお、途中で target との差分が0になった場合はそれ以上探索する必要がないので処理を中止します。
for i, x in enumerate(nums_sorted):
if i > len(nums_sorted) - 2:
break
L = R = 0 # yとzのポインタ
while(i + L + 1 < len(nums_sorted) - R - 1): y < z である限り
y = nums_sorted[i + L + 1]
z = nums_sorted[len(nums_sorted) - R - 1]
dif = x + y + z - target # x + y + zとtargetの差分
if abs(dif) < min_dif: # 差分が暫定値より小さければ
ans = x + y + z # 答えの更新
min_dif = abs(dif) # 最小差分の更新
if dif < 0 : L += 1 # 差分が0より小さければ（x+y+z < target）yを進める
elif dif > 0 : R += 1 # 差分が0より多きければ（x+y+z > target）zを進める
else : return ans # それ以外(x+y+z == target)ならばansを返すコード
コード全文です。
class Solution:
def threeSumClosest(self, nums: list[int], target: int) -> int:
nums_sorted = sorted(nums) # numsをソート
ans = min_dif = 1e10
for i, x in enumerate(nums_sorted):
if i > len(nums_sorted) - 2:
break
L = R = 0
while(i + L + 1 < len(nums_sorted) - R - 1):
y = nums_sorted[i + L + 1]
z = nums_sorted[len(nums_sorted) - R - 1]
dif = x + y + z - target
if abs(dif) < min_dif:
ans = x + y + z
min_dif = abs(dif)
if dif < 0 : L += 1
elif dif > 0 : R += 1
else : return ans
return ans計算量はO(N2)です。
コードはgithubにも保管しています。
結果
今回で10回目です。
100回目まではなるべく毎日更新頑張りたいと思います。
すでに2さぼってしまいましたが。。。
コメント