ゼロから始める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] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don’t satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= target <= 10^6

解法

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        ans,mod = 0,10**9+7
        nums.sort()
        for i,j in enumerate(nums):
            if target < j*2:
                break
            b = bisect.bisect(nums,target-j,lo=i)
            ans += pow(2, b-i-1, mod)
        return ans % mod
# Runtime: 888 ms, faster than 82.84% of Python3 online submissions for Number of Subsequences That Satisfy the Given Sum Condition.
# Memory Usage: 25.2 MB, less than 100.00% of Python3 online submissions for Number of Subsequences That Satisfy the Given Sum Condition.

問題文で指定されている通り、最初にmod(10**9+7)を指定し、for文の中で二分探索をする、という書き方をしました。
bisectの引数は以下の通りです。

bisect(a,b,(lo,hi))

a: リスト
b: 挿入する値
lo: 探索範囲の下限
hi: 探索範囲の上限

なお、この記事を読む方の中にはご存知の方が多いと思いますが、二分探索はソートされていることが前提条件なので、コードの最初の方でリストをソートしてあります。例を見る限りソートされてない場合も多そうだったしね・・・

ちなみに10**9+7、というのは他の競技プログラミングをやる上で（たくさんサイトがあるのでどれか一つに限らず）結構出てきたりします。
それについての分かりやすい解説記事を書いてくださっている方もいるので気になる方は是非そちらもどうぞ。

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