ゼロから始めるLeetCode Day72 「1498. Number of Subsequences That Satisfy the Given Sum Condition」
概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day71 「1496. Path Crossing」 次回 ゼロから始めるLeetCode Day73 「1491. Average Salary Excluding the Minimum and Maximum Salary」 Twitter やってます。 問題 1498. Number of Subsequences That Satisfy the Given Sum Condition 難易度はMedium。 問題としては、整数の配列 nums と整数 target が与えられます。 numsの最小値と最大値の和が目標値以下になるような、空ではない部分列の数を返します。 答えが大きすぎるかもしれないので、10^9 + 7の剰余演算を返します。 Example 1: Input: nums = [3,5,6,7], target = 9 Output: 4 Explanation: There are 4 subsequences that satisfy the condition. [3] -> Min value + max value <= target (3 + 3 <= 9) [3,5] -> (3 + 5 <= 9) [3,5,6] -> (