难度: Medium
Submission
运行时间: 147 ms
内存: 16.3 MB
### my: DFS 808/812---超时
# class Solution:
# def divisibleTripletCount(self, nums: List[int], d: int) -> int:
# self.ans=0
# n=len(nums)
# def dfs(x,cul,cnt):
# # cul+=nums[x]
# if cnt==3:
# if cul%d==0:
# self.ans+=1
# return
# # if x==n-1:
# # return
# for y in range(x,n):
# # if y+1<n:
# dfs(y+1,cul+nums[y],cnt+1)
# dfs(0,0,0)
# return self.ans
# from collections import Counter
# class Solution:
# def divisibleTripletCount(self, nums: List[int], d: int) -> int:
# cnt=Counter(nums)
# keys=list(cnt.keys())
# n=len(keys)
# self.ans=0
# for k,v in cnt.items():
# if v>=3 and (3*k==d or k==d):
# self.ans+=v*(v-1)*(v-2)//6
# def dfs(x,k,path):
# if k==3:
# su=sum(path)
# if su%d==0:
# self.ans+=cnt[path[0]]*cnt[path[1]]*cnt[path[2]]
# return
# for y in range(x,n):
# path.append(keys[y])
# dfs(y+1,k+1,path)
# path.pop(keys[y])
# return self.ans
### 网：余数法
# 固定中间数，左右两侧分别用字典统计取模为d的数值个数，左右侧数量相乘即可
from collections import defaultdict
class Solution:
def divisibleTripletCount(self,nums,d):
s1,s2=defaultdict(int),defaultdict(int)
for x in nums:
s2[x%d]+=1
res=0
for i in range(len(nums)):
x=nums[i]
s2[x%d]-=1
if i:
s1[nums[i-1]%d]+=1
for k in s1:
# res+=s1[k]*s2[(2*d-x%d-k)%d] ### 写法1
# res+=s1[k]*s2[abs(x%d+k-d)%d]
res+=s1[k]*s2[(d-(x%d+k)%d)%d] ### 写法2 （my）
return res
Explain
题解采用了一种余数法来找出数组中能被整数d整除的三元组数量。该方法的核心思想是将问题转化为两个前缀和后缀的余数统计问题。对于数组中的每个元素x，固定x为三元组的中间元素，并统计在x左侧和右侧出现的余数的频率。通过这种方式，可以快速计算出以x为中心，符合条件的三元组数量。具体来说，对于每个x，通过查看左侧余数为k的数量和右侧余数为(d-(x%d+k)%d)%d的数量，通过相乘即可得到以x为中心的符合条件的三元组个数。
时间复杂度: O(n*d)
空间复杂度: O(d)
# 余数法解决问题的代码实现
from collections import defaultdict
class Solution:
def divisibleTripletCount(self, nums, d):
s1, s2 = defaultdict(int), defaultdict(int)
# 初始化右侧余数统计
for x in nums:
s2[x % d] += 1
res = 0
for i in range(len(nums)):
x = nums[i]
# 更新右侧余数统计
s2[x % d] -= 1
# 更新左侧余数统计
if i:
s1[nums[i-1] % d] += 1
# 计算符合条件的三元组数量
for k in s1:
res += s1[k] * s2[(d - (x % d + k) % d) % d]
return res
Explore
在算法实现中，为了避免左侧和右侧余数统计相互干扰，我们分别维护了两个字典`s1`和`s2`来记录左侧和右侧的余数频率。在遍历数组的过程中，我们先更新右侧余数统计（即在处理当前元素`x`之前从`s2`中减去`x % d`的计数），然后处理当前元素，最后更新左侧余数统计（即在处理下一个元素之前将当前元素加入`s1`）。这种处理方式确保在计算以当前元素为中心的三元组时，左右两侧的数据是独立且准确的。
每次循环在处理一个元素`x`时，只需要将这个元素从右侧余数统计`s2`中减去，因为只有这个元素即将被考虑到左侧或者被固定为中心元素。这种方式可以有效减少不必要的操作，因为只有当前元素`x`从右侧转移到左侧或者作为中心元素时，右侧的统计数据才需要更新。其他余数值没有变化，因此不需要调整。
这个表达式用于计算右侧需要的特定余数，以确保整个三元组的和能够被`d`整除。具体来说，`x % d`是中心元素`x`的余数，`k`是左侧余数。根据整除的性质，三个数的和被`d`整除的条件是这三个数的余数和也应该被`d`整除。因此，表达式`d - (x % d + k) % d) % d`计算的是，给定左侧的余数`k`和中心的余数`x % d`后，右侧的数需要满足的余数条件。这样，只要右侧的余数频率中存在符合这个计算结果的余数，就可以与左侧的`k`和中心的`x`组成符合条件的三元组。