ゼロから始めるLeetCode Day65「560. Subarray Sum Equals K

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day64「287. Find the Duplicate Number」

次回
ゼロから始めるLeetCode Day66「438. Find All Anagrams in a String」

Twitterやってます。

問題

560. Subarray Sum Equals K
難易度はMedium。
Top 100 Liked Questionsからの抜粋です。

整数の配列と整数 k が与えられたとき，和が k に等しい連続部分配列の総数を求めよ、という問題です。

Example 1:
Input:nums = [1,1,1], k = 2
Output: 2

Constraints:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

解法

import collections

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dic = defaultdict(int)
        dic[0] = 1
        count = calc = 0
        for n in nums:
            calc += n
            dic[calc],count = dic[calc] + 1,count + dic[calc-k],
        return count
# Runtime: 144 ms, faster than 44.41% of Python3 online submissions for Subarray Sum Equals K.
# Memory Usage: 17.9 MB, less than 10.96% of Python3 online submissions for Subarray Sum Equals K.

defaultdictを使って書きました。

制約についてはそこまで意識せず、ひとまず解くにはどうやったら良いかを考えました。
calcで累積和を保持し、辞書を使ってkeyの部分で値を保持し、valueの部分で連続で同値が出現した回数を保存し、そして和に遭遇した回数も差し引いたものdic[calc-k]で保持することにより、countに要求に沿った値が加算されていく、というものです。

ヒントをSolutionからもらって書きましたがすごくしっくりきますね。

そういえば専門的なアルゴリズムの講義を受けたことがないのですが、思えば他の人がどうやってアルゴリズムを書いているのかをよく知らないんですよね。

僕の考え方は

一旦プログラミングのことを考えずにどうやって書くかをぼんやり考える
↓
良さそうな考え方がつかめたら適当に紙とかに書いてちゃんと正しいフローになっているかを考える
↓
Pythonでそのフローを実現するために良さげなライブラリや組み込み関数があるか調べて書く
↓
完成

という流れです。
上手くいかない場合はフローを見直して手直ししたりざっくり新しいパターンを書いたり、といった風にしていて、僕の課題はフローを考えるところにあるのかなぁと思ったりしています。（もちろん典型的なアルゴリズムやデータ構造に関してもまだまだ勉強不足ですが）
高校生の時に真剣に受験数学というものに取り組んでこなかったですし、整数や確率、場合の数などについて聞かれると面食らう場合が多いんですよね。

割とそこについての課題を克服するために数学の問題をコツコツ解いたりしているのですが、やはりやりたいことがあってその過程で学ぶ数学はやってて楽しいものがありますね。
学生時代は数学で何かをやりたいと思っていなかったので、新鮮な気持ちで取り組めています。

では今回はここまで、お疲れ様でした。