Skip to content

Latest commit

 

History

History
227 lines (191 loc) · 6.41 KB

README.md

File metadata and controls

227 lines (191 loc) · 6.41 KB

2198. 单因数三元组

English Version

题目描述

给定一个下标从 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 <= 105
  • 1 <= nums[i] <= 100

解法

Python3

class Solution:
    def singleDivisorTriplet(self, nums: List[int]) -> int:
        def check(a, b, c):
            s = a + b + c
            return sum(s % x == 0 for x in [a, b, c]) == 1

        counter = Counter(nums)
        ans = 0
        for a, cnt1 in counter.items():
            for b, cnt2 in counter.items():
                for c, cnt3 in counter.items():
                    if check(a, b, c):
                        if a == b:
                            ans += cnt1 * (cnt1 - 1) * cnt3
                        elif a == c:
                            ans += cnt1 * (cnt1 - 1) * cnt2
                        elif b == c:
                            ans += cnt1 * cnt2 * (cnt2 - 1)
                        else:
                            ans += cnt1 * cnt2 * cnt3
        return ans

Java

class Solution {
    public long singleDivisorTriplet(int[] nums) {
        int[] counter = new int[101];
        for (int x : nums) {
            ++counter[x];
        }
        long ans = 0;
        for (int i = 1; i <= 100; ++i) {
            for (int j = 1; j <= 100; ++j) {
                for (int k = 1; k <= 100; ++k) {
                    int cnt1 = counter[i], cnt2 = counter[j], cnt3 = counter[k];
                    int s = i + j + k;
                    int cnt = 0;
                    if (s % i == 0) {
                        ++cnt;
                    }
                    if (s % j == 0) {
                        ++cnt;
                    }
                    if (s % k == 0) {
                        ++cnt;
                    }
                    if (cnt != 1) {
                        continue;
                    }
                    if (i == j) {
                        ans += (long) cnt1 * (cnt1 - 1) * cnt3;
                    } else if (i == k) {
                        ans += (long) cnt1 * (cnt1 - 1) * cnt2;
                    } else if (j == k) {
                        ans += (long) cnt1 * cnt2 * (cnt2 - 1);
                    } else {
                        ans += (long) cnt1 * cnt2 * cnt3;
                    }
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long singleDivisorTriplet(vector<int>& nums) {
        vector<int> counter(101);
        for (int& x : nums) ++counter[x];
        long long ans = 0;
        for (int i = 1; i <= 100; ++i) {
            for (int j = 1; j <= 100; ++j) {
                for (int k = 1; k <= 100; ++k) {
                    int cnt1 = counter[i], cnt2 = counter[j], cnt3 = counter[k];
                    int s = i + j + k;
                    int cnt = (s % i == 0) + (s % j == 0) + (s % k == 0);
                    if (cnt != 1) continue;
                    if (i == j)
                        ans += 1ll * cnt1 * (cnt1 - 1) * cnt3;
                    else if (i == k)
                        ans += 1ll * cnt1 * (cnt1 - 1) * cnt2;
                    else if (j == k)
                        ans += 1ll * cnt1 * cnt2 * (cnt2 - 1);
                    else
                        ans += 1ll * cnt1 * cnt2 * cnt3;
                }
            }
        }
        return ans;
    }
};

Go

func singleDivisorTriplet(nums []int) int64 {
	counter := make([]int, 101)
	for _, x := range nums {
		counter[x]++
	}
	var ans int64
	check := func(a, b, c int) bool {
		s := a + b + c
		cnt := 0
		if s%a == 0 {
			cnt++
		}
		if s%b == 0 {
			cnt++
		}
		if s%c == 0 {
			cnt++
		}
		return cnt == 1
	}
	for i := 1; i <= 100; i++ {
		for j := 1; j <= 100; j++ {
			for k := 1; k <= 100; k++ {
				if check(i, j, k) {
					cnt1, cnt2, cnt3 := counter[i], counter[j], counter[k]
					if i == j {
						ans += int64(cnt1 * (cnt1 - 1) * cnt3)
					} else if i == k {
						ans += int64(cnt1 * (cnt1 - 1) * cnt2)
					} else if j == k {
						ans += int64(cnt1 * cnt2 * (cnt2 - 1))
					} else {
						ans += int64(cnt1 * cnt2 * cnt3)
					}
				}
			}
		}
	}
	return ans
}

TypeScript



...