| comments | difficulty | edit_url | tags | |
|---|---|---|---|---|
true |
中等 |
|
给定一个下标从 0 开始的正整数数组 nums。由三个 不同 索引 (i, j, k) 组成的三元组，如果 nums[i] + nums[j] + nums[k] 能被 nums[i]、nums[j] 或 nums[k] 中的 一个 整除，则称为 nums 的 单因数三元组。
返回 nums 的单因数三元组。
示例 1:
输入: nums = [4,6,7,3,2] 输出: 12 解释: 三元组索引 (0, 3, 4), (0, 4, 3), (3, 0, 4), (3, 4, 0), (4, 0, 3), 和 (4, 3, 0) 的值为 [4, 3, 2] (或者说排列为 [4, 3, 2]). 4 + 3 + 2 = 9 只能被 3 整除，所以所有的三元组都是单因数三元组。 三元组索引 (0, 2, 3), (0, 3, 2), (2, 0, 3), (2, 3, 0), (3, 0, 2), 和 (3, 2, 0) 的值为 [4, 7, 3] (或者说排列为 [4, 7, 3]). 4 + 7 + 3 = 14 只能被 7 整除，所以所有的三元组都是单因数三元组。 一共有 12 个单因数三元组。
示例 2:
输入: nums = [1,2,2] 输出: 6 提示: 三元组索引 (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), 和 (2, 1, 0) 的值为 [1, 2, 2] (或者说排列为 [1, 2, 2]). 1 + 2 + 2 = 5 只能被 1 整除，所以所有的三元组都是单因数三元组。 一共有6个单因数三元组。
示例 3:
输入: nums = [1,1,1] 输出: 0 提示: 没有单因数三元组。 注意 (0, 1, 2) 不是单因数三元组。 因为 nums[0] + nums[1] + nums[2] = 3，3 可以被 nums[0], nums[1], nums[2] 整除。
提示:
3 <= nums.length <= 1051 <= nums[i] <= 100
我们注意到，数组
- 如果
$a = b$ ，那么以$a, b, c$ 为元素的单因数三元组的个数为$x \times (x - 1) \times z$ ，其中$x$ ,$y$ ,$z$ 分别表示$a$ ,$b$ ,$c$ 在数组$\textit{nums}$ 中出现的次数。 - 如果
$a = c$ ，那么以$a, b, c$ 为元素的单因数三元组的个数为$x \times (x - 1) \times y$ 。 - 如果
$b = c$ ，那么以$a, b, c$ 为元素的单因数三元组的个数为$x \times y \times (y - 1)$ 。 - 如果
$a, b, c$ 互不相等，那么以$a, b, c$ 为元素的单因数三元组的个数为$x \times y \times z$ 。
最后，我们将所有的单因数三元组的个数相加即可。
时间复杂度
class Solution:
def singleDivisorTriplet(self, nums: List[int]) -> int:
cnt = Counter(nums)
ans = 0
for a, x in cnt.items():
for b, y in cnt.items():
for c, z in cnt.items():
s = a + b + c
if sum(s % v == 0 for v in (a, b, c)) == 1:
if a == b:
ans += x * (x - 1) * z
elif a == c:
ans += x * (x - 1) * y
elif b == c:
ans += x * y * (y - 1)
else:
ans += x * y * z
return ansclass Solution {
public long singleDivisorTriplet(int[] nums) {
int[] cnt = new int[101];
for (int x : nums) {
++cnt[x];
}
long ans = 0;
for (int a = 1; a <= 100; ++a) {
for (int b = 1; b <= 100; ++b) {
for (int c = 1; c <= 100; ++c) {
int s = a + b + c;
int x = cnt[a], y = cnt[b], z = cnt[c];
int t = 0;
t += s % a == 0 ? 1 : 0;
t += s % b == 0 ? 1 : 0;
t += s % c == 0 ? 1 : 0;
if (t == 1) {
if (a == b) {
ans += 1L * x * (x - 1) * z;
} else if (a == c) {
ans += 1L * x * (x - 1) * y;
} else if (b == c) {
ans += 1L * x * y * (y - 1);
} else {
ans += 1L * x * y * z;
}
}
}
}
}
return ans;
}
}class Solution {
public:
long long singleDivisorTriplet(vector<int>& nums) {
int cnt[101]{};
for (int x : nums) {
++cnt[x];
}
long long ans = 0;
for (int a = 1; a <= 100; ++a) {
for (int b = 1; b <= 100; ++b) {
for (int c = 1; c <= 100; ++c) {
int s = a + b + c;
int x = cnt[a], y = cnt[b], z = cnt[c];
int t = (s % a == 0) + (s % b == 0) + (s % c == 0);
if (t == 1) {
if (a == b) {
ans += 1LL * x * (x - 1) * z;
} else if (a == c) {
ans += 1LL * x * (x - 1) * y;
} else if (b == c) {
ans += 1LL * x * y * (y - 1);
} else {
ans += 1LL * x * y * z;
}
}
}
}
}
return ans;
}
};func singleDivisorTriplet(nums []int) (ans int64) {
cnt := [101]int{}
for _, x := range nums {
cnt[x]++
}
f := func(a, b int) int {
if a%b == 0 {
return 1
}
return 0
}
for a := 1; a <= 100; a++ {
for b := 1; b <= 100; b++ {
for c := 1; c <= 100; c++ {
s := a + b + c
t := f(s, a) + f(s, b) + f(s, c)
if t == 1 {
if a == b {
ans += int64(cnt[a] * (cnt[a] - 1) * cnt[c])
} else if a == c {
ans += int64(cnt[a] * (cnt[a] - 1) * cnt[b])
} else if b == c {
ans += int64(cnt[b] * (cnt[b] - 1) * cnt[a])
} else {
ans += int64(cnt[a] * cnt[b] * cnt[c])
}
}
}
}
}
return
}function singleDivisorTriplet(nums: number[]): number {
const cnt: number[] = Array(101).fill(0);
for (const x of nums) {
++cnt[x];
}
let ans = 0;
const f = (a: number, b: number) => (a % b === 0 ? 1 : 0);
for (let a = 1; a <= 100; ++a) {
for (let b = 1; b <= 100; ++b) {
for (let c = 1; c <= 100; ++c) {
const s = a + b + c;
const t = f(s, a) + f(s, b) + f(s, c);
if (t === 1) {
if (a === b) {
ans += cnt[a] * (cnt[a] - 1) * cnt[c];
} else if (a === c) {
ans += cnt[a] * (cnt[a] - 1) * cnt[b];
} else if (b === c) {
ans += cnt[b] * (cnt[b] - 1) * cnt[a];
} else {
ans += cnt[a] * cnt[b] * cnt[c];
}
}
}
}
}
return ans;
}