ゼロから始めるLeetCode Day75 「15. 3Sum」
概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day74 「12. Integer to Roman」
次回
ゼロから始めるLeetCode Day76「3. Longest Substring Without Repeating Characters」
Twitterやってます。
問題
15. 3Sum
難易度はMedium。
問題としては、n個の整数の配列numsがあるとすると、numsにa + b + c = 0となる要素a, b, cがあるかどうかを確認するアルゴリズムを設計し、0の和を与える配列の中のすべてのユニークな三重項を求めよ。
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
解法
3つ選び、0になる組み合わせを選べ、というものです。
組み合わせの鉄則とも言えるかもしれませんが、先に何を固定するかを決めたほうが良いと思います。
今回は以下のように書きました。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
left = i+1
right = len(nums)-1
while left < right:
sums = nums[i]+nums[left]+nums[right]
if sums < 0:
left += 1
elif sums > 0:
right -= 1
else:
ans.append([nums[i],nums[left],nums[right]])
while left < right and nums[left]==nums[left+1]:
left += 1
while left > right and nums[right]==nums[right-1]:
right -= 1
left += 1
right -= 1
return ans
# Runtime: 1092 ms, faster than 45.79% of Python3 online submissions for 3Sum.
# Memory Usage: 17.1 MB, less than 76.15% of Python3 online submissions for 3Sum.
まず最初にソートすることによって昇順に並べ替えます。
こうすることで前から要素をfor文で回していった時に要素の大小の指定がしやすくなります。
具体的な例を上げるならば、これを
[-1,0,1,2,-1,-4]
ソートすると、
[-4,-1,-1,0,1,2]
という風になります。
これの要素を最初から舐めていくときに、どういう風に3sumのうちの残りの二つの要素をどうやって選択していくべきかがこの問題の核と言えるでしょう。
コードで書いたように、僕はi+1をleft,len(nums)-1をrightとし、仮にそれらを足した時にそれらの合計値であるsumsが0より小さければleftの要素を+1、0より大きければrightを-1することで解決しました。
これは上でも述べたソートをしているからできることです。
実際には
-4+(-1)+2=-3<0
なので、leftの要素を動かして、
-4+(-1)+2=-3<0
これでも一緒なのでまたleftの要素を動かして
-4+0+2=-2<0
といった風なフローとなっています。
そして仮にそれら以外、すなわちsums==0となった場合は用意していたansに要素を追加する、というものです。
こういった和の組み合わせ系は今回のような形式で解くのが楽な気がするので典型的な問題としてしっかり覚えておきたいですね。
にしても昨日と打って変わって良問でした。
では今回はここまで。お疲れ様でした。
コメント
コメントを投稿