Skip to content
TheChatArchiveThe Chat Archive
o3-mini· OpenAIHugging Face LMArena Human Preference 140K

给你一个下标从 0 开始的整数数组 nums ,以及整数 modulo 和整数 k 。 请你找出并统计数组中 趣味子数组 的数目。 如果 子数组 nums[l..r]…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with DeepSeekdeepseek-v3-0324’s answer.
  1. User

    给你一个下标从 0 开始的整数数组 nums ,以及整数 modulo 和整数 k 。

    请你找出并统计数组中 趣味子数组 的数目。

    如果 子数组 nums[l..r] 满足下述条件,则称其为 趣味子数组 :

    在范围 [l, r] 内,设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。 以整数形式表示并返回趣味子数组的数目。

    注意:子数组是数组中的一个连续非空的元素序列。

    class Solution: def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:

  2. Assistant

    我们可以利用前缀和的思想来解决这个问题。记下前缀和数组 ( P ) 其中

    [ P[i+1] = P[i] + \mathbf{1}{,nums[i] % modulo == k,} ]

    其中 (\mathbf{1}{\cdot}) 表示判断是否满足条件,满足为 1,否则为 0。那么区间 ([l,r]) 内满足条件的元素个数为 [ cnt = P[r+1] - P[l] ] 题目要求 [ cnt % modulo == k ] 利用模运算的性质,上式等价于 [ (P[r+1] - P[l]) % modulo == k \quad\Longleftrightarrow\quad P[r+1] % modulo == (P[l] + k) % modulo ]

    因此对于每个前缀 ( P[j] ) (其中 ( j = r+1 )),我们希望统计有多少个 ( i ) (对应 ( l )),使得 [ P[i] \equiv P[j]-k ; (\bmod; modulo). ] 我们可以边遍历数组边统计前缀模值的出现次数,从而在 ( O(n) ) 时间内求出答案。

    下面给出完整的代码实现:


    class Solution:
        def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
            # freq 用来记录前缀 P[i] (i 从 0 到 n)  的模 modulo 的值出现的次数
            freq = {0: 1}  # 初始时 P[0] = 0
            prefix = 0  # 当前前缀和(计数)
            res = 0
            
            for num in nums:
                # 如果当前数字满足条件,则累加 1
                if num % modulo == k:
                    prefix += 1
                # 当前前缀模 modulo 的值
                cur_mod = prefix % modulo
                # 如果存在之前的前缀使得: prior_mod = (cur_mod - k) % modulo,则 [l, r] 便是合法子数组
                need_mod = (cur_mod - k) % modulo
                res += freq.get(need_mod, 0)
                # 更新 freq
                freq[cur_mod] = freq.get(cur_mod, 0) + 1
            
            return res
    

    说明

    1. 前缀定义:我们定义 prefix 为当前前缀中满足 nums[i] % modulo == k 的元素个数。
    2. 子数组与前缀差:对于子数组 [l, r],其“计数”即为 ( P[r+1]-P[l] )。因此要求 ((P[r+1]-P[l]) % modulo == k),这可以转换为 ( P[r+1] % modulo == (P[l] + k) % modulo )。
    3. 计数方法:遍历数组时,我们统计每个前缀模值出现的次数,对于当前前缀 cur_mod,只需要找到之前出现次数中,模值等于 ((cur_mod - k) % modulo) 的个数即可。这些配对的前缀组合对应一个合法的子数组。
    4. 边界:初始时 freq={0:1} 对应空前缀 (P[0]=0);这样当子数组从数组起始位置开始时也能正确计数。

    这种方法能够在线性时间内统计所有满足条件的子数组。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.