摘要
Title: 2845. 统计趣味子数组的数目
Categories: 模运算、前缀和、哈希表

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

2845. 统计趣味子数组的数目

题意

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

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

如果 子数组 nums[l…r] 满足下述条件，则称其为 趣味子数组 ：

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

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

思路

https://leetcode.cn/problems/count-of-interesting-subarrays/solutions/2424063/qian-zhui-he-ha-xi-biao-fu-ti-dan-by-end-74bb/

我们需要找到数组中所有满足 (s[r+1] - s[l]) % modulo == k 的子数组数量。其中 s[i] 表示前缀和，第 i 个前缀和表示数组 nums 从开头到第 i 个元素的和。

设：

• s[r+1] 是从开头到第 r+1 个元素的前缀和
• s[l] 是从开头到第 l 个元素的前缀和

我们需要找到所有满足

$$(s[r+1] - s[l]) \% modulo == k$$

的 (r+1, l) 对。
可得

$$s[l] \% modulo = (s[r+1]−k) \% modulo$$

(a+b)%mod=k⟹(a%mod+b%mod)%mod=k
(a×b)%mod=k⟹((a%mod)×(b%mod))%mod=k
(a−b)%mod=k⟹(b%mod+k)%mod=a%mod
(a×b^(−1))%mod=k⟹(a%mod×b^(-1)%mod)%mod=k
(a/b)%mod=k⟹(a%mod×b^(mod−2))%mod=k

代码

'''
Author: NEFU AB-IN
Date: 2024-07-25 20:43:52
FilePath: \LeetCode\2845\2845.py
LastEditTime: 2024-07-25 21:20:11
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        n = len(nums)
        prefix = Arr.array(0, n + 1)
        for i, num in enumerate(nums, 1):
            prefix[i] = prefix[i - 1] + (1 if num % modulo == k else 0)
        map_ = Counter()
        ans = 0
        for pre in prefix:
            mod_value = pre % modulo
            target_value = (mod_value - k + modulo) % modulo
            ans += map_[target_value]
            map_[mod_value] += 1
        return ans