标签: 数学
难度: Medium
Submission
运行时间: 208 ms
内存: 22.5 MB
g=defaultdict(list)
for i in range(1,101):
for j in range(1,101):
for k in range(j,101):
if (i+j+k)%i==0 and (i+j+k)%j!=0 and (i+j+k)%k!=0:
g[i].append((j,k))
class Solution:
def singleDivisorTriplet(self, nums: List[int]) -> int:
res=0
cnt=Counter(nums)
for a in set(nums):
for b,c in g[a]:
if b!=c:
res+=cnt[a]*cnt[b]*cnt[c]*6
else:
res+=cnt[a]*comb(cnt[b],2)*6
return res
Explain
本题解首先使用一个嵌套的循环构建一个字典 g，字典的键为 i，值为满足特定条件的二元组 (j, k) 的列表。特定条件是：i+j+k 除以 i 的余数为 0，除以 j 和 k 的余数不为 0。这表示 i 是 i+j+k 的唯一因子。在 Solution 类的 singleDivisorTriplet 方法中，首先初始化结果 res 为 0，并使用计数器 cnt 来记录 nums 中每个数字的出现次数。遍历 nums 中的唯一数字 a，对于每个 a，从字典 g 中找到所有符合条件的 (b, c)。如果 b 和 c 不相等，计算可能的三元组数量，并乘以 6（因为三元组 (a, b, c) 可以有 6 种不同的排列）。如果 b 和 c 相等，则需要特殊处理，使用组合数计算 b 选 2 的方式，并同样乘以 6。最终，返回计算出的结果 res。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
g=defaultdict(list) # 创建一个默认为列表的字典
for i in range(1,101): # i 从 1 到 100
for j in range(1,101): # j 从 1 到 100
for k in range(j,101): # k 从 j 到 100，确保 k >= j
if (i+j+k)%i==0 and (i+j+k)%j!=0 and (i+j+k)%k!=0: # 检查条件
g[i].append((j,k)) # 添加满足条件的二元组到字典
class Solution:
def singleDivisorTriplet(self, nums: List[int]) -> int:
res=0 # 结果初始化为 0
cnt=Counter(nums) # 计数 nums 中每个元素的出现次数
for a in set(nums): # 遍历 nums 中的每个唯一元素
for b,c in g[a]: # 遍历字典中与 a 关联的所有 (b, c) 对
if b!=c: # 如果 b 和 c 不相同
res+=cnt[a]*cnt[b]*cnt[c]*6 # 计算排列组合的数量
else: # 如果 b 和 c 相同
res+=cnt[a]*comb(cnt[b],2)*6 # 使用组合计算数量
return res # 返回结果
Explore
这个设计是为了确保在三元组中，i是唯一的因子。如果i+j+k除以i的余数为0，说明i是i+j+k的因子。如果i+j+k除以j和k的余数都不为0，则j和k不是i+j+k的因子。这样设计确保了i是三个数之和i+j+k的唯一因子，满足题目的单因数三元组的要求。
将k的循环起始于j（k从j开始）的设计是为了避免在字典g中重复记录元组，同时确保b和c的关系（b <= c）不会影响组合的对称性。这样做可以避免不必要的计算和存储重复的数据，例如避免记录(b, c)和(c, b)两次，优化了空间和计算效率。
当b和c相等时，元素b在数组中的实际可用数量会影响可能的组合。使用组合数计算方式是因为需要从数量为cnt[b]的b中选择两个来组成三元组，这里的组合数计算方式为comb(cnt[b], 2)，表示从cnt[b]个b中选择两个的不同方式。这种计算方式确保了在b和c相等时计数的正确性和公平性。
使用defaultdict(list)来构建字典g的好处在于，当访问一个尚未在字典中存在的键时，defaultdict会自动为该键创建一个新的空列表。这样可以避免在添加元素之前需要检查键是否存在于字典中，从而简化代码并提高效率。defaultdict(list)在处理这种类型的数据累积场景中特别有用，使代码更加简洁和高效。