配列 / 文字列（応用）累積和（Prefix Sum） | Coding InterviewCat

配列 / 文字列（応用）累積和（Prefix Sum）

LeetCode 練習問題集

問題	難易度	重要度	テクニック
Running Sum of 1d Array	★	高	累積和
Maximum Score After Splitting a String	★★	高	累積和
Product of Array Except Self	★★★	高	累積和
Sum of Absolute Differences in a Sorted Array	★★★	高	累積和
Maximum Good Subarray Sum	★★★	高	累積和
Subarray Sum Equals K	★★★	中	累積和（ハッシュテーブル）
Subarray Sums Divisible by K	★★★	中	累積和（ハッシュテーブル）

累積和（Prefix Sum）とは事前に配列の総和を計算しておく事で任意の区間の和をO(1)で計算できるアルゴリズムです。例えば、任意の区間の和を計算するクエリを何度も呼び出す際に活用する事ができます。非常によく活用されるアルゴリズムです。部分配列の和と聞いたら真っ先に適用できないかを考えてみましょう。

Maximum subarray

難易度:★★ 重要度: 高

テック企業求人一覽

こちらの求人をrecoから紹介されたものです。 recoは現役の外資エンジニアがモックインタビュー付きで面接対策を行ってくれる転職サービスです。これらの企業にどのように準備に準備して振る舞えば採用されるのか的確なアドバイスを受ける事ができます。 InterviewCatの共著者のgaijineersさんが創業者として皆さんの転職をサポートします。