标签： 数学

目标

一个 平方和三元组 (a,b,c) 指的是满足 a² + b² = c² 的 整数 三元组 a，b 和 c 。

给你一个整数 n ，请你返回满足 1 <= a, b, c <= n 的 平方和三元组 的数目。

示例 1：

输入：n = 5
输出：2
解释：平方和三元组为 (3,4,5) 和 (4,3,5) 。

示例 2：

输入：n = 10
输出：4
解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10) 。

说明：

• 1 <= n <= 250

思路

统计满足 a² + b² = c²，且 1 <= a,b,c <= n 的三元组个数。

暴力枚举 a b，判断平方和是否小于 n²，同时判断开根号之后是否是整数。

代码

/**
 * @date 2025-12-08 8:55
 */
public class CountTriples1925 {

    public int countTriples(int n) {
        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i && i * i + j * j <= n * n; j++) {
                int s = i * i + j * j;
                int k = (int) Math.sqrt(s);
                if (s == k * k){
                    res++;
                }
            }
        }
        return res * 2;
    }

}

性能

目标

给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。

示例 1：

输入：low = 3, high = 7
输出：3
解释：3 到 7 之间奇数数字为 [3,5,7] 。

示例 2：

输入：low = 8, high = 10
输出：1
解释：8 到 10 之间奇数数字为 [9] 。

说明：

• 0 <= low <= high <= 10^9

思路

返回 low 到 high 之间的奇数数目。

如果数字个数是偶数，返回 (high - low + 1) / 2，否则，取决于 high 是奇数还是偶数，如果是奇数，需要再额外加上 1。

代码

/**
 * @date 2025-12-07 22:22
 */
public class CountOdds1523 {

    public int countOdds(int low, int high) {
        int n = high - low + 1;
        return n / 2 + (n % 2 == 0 ? 0 : high % 2);
    }
}

性能

目标

给你一个长度为 n 的整数数组 nums 。

分区 是指将数组按照下标 i （0 <= i < n - 1）划分成两个 非空 子数组，其中：

• 左子数组包含区间 [0, i] 内的所有下标。
• 右子数组包含区间 [i + 1, n - 1] 内的所有下标。

对左子数组和右子数组先求元素 和 再做 差 ，统计并返回差值为 偶数 的 分区 方案数。

示例 1：

输入：nums = [10,10,3,7,6]
输出：4
解释：
共有 4 个满足题意的分区方案：
[10]、[10, 3, 7, 6] 元素和的差值为 10 - 26 = -16 ，是偶数。
[10, 10]、[3, 7, 6] 元素和的差值为 20 - 16 = 4，是偶数。
[10, 10, 3]、[7, 6] 元素和的差值为 23 - 13 = 10，是偶数。
[10, 10, 3, 7]、[6] 元素和的差值为 30 - 6 = 24，是偶数。

示例 2：

输入：nums = [1,2,2]
输出：0
解释：
不存在元素和的差值为偶数的分区方案。

示例 3：

输入：nums = [2,4,6,8]
输出：3
解释：
所有分区方案都满足元素和的差值为偶数。

说明：

• 2 <= n == nums.length <= 100
• 1 <= nums[i] <= 100

思路

将数组 nums 划分为非空的左右两部分，满足左子数组的元素和与右子数组的元素和之差为偶数，返回划分的方案数。

数组所有元素和为 sum，假设左子数组和为 left，那么右子树和为 sum - left，二者之差为 2 * left - sum，只需判断 sum 是否是偶数即可，如果是偶数，有 n - 1 种方案，否则没有满足要求的方案。

代码

/**
 * @date 2025-12-05 9:10
 */
public class CountPartitions3432 {

    public int countPartitions(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum % 2 == 0 ? nums.length - 1 : 0;
    }
}

性能

目标

给你一个整数数组 nums 和一个整数 k。你可以执行以下操作任意次：

• 选择一个下标 i，并将 nums[i] 替换为 nums[i] - 1。

返回使数组元素之和能被 k 整除所需的最小操作次数。

示例 1：

输入： nums = [3,9,7], k = 5
输出： 4
解释：
对 nums[1] = 9 执行 4 次操作。现在 nums = [3, 5, 7]。
数组之和为 15，可以被 5 整除。

示例 2：

输入： nums = [4,1,3], k = 4
输出： 0
解释：
数组之和为 8，已经可以被 4 整除。因此不需要操作。

示例 3：

输入： nums = [3,2], k = 6
输出： 5
解释：
对 nums[0] = 3 执行 3 次操作，对 nums[1] = 2 执行 2 次操作。现在 nums = [0, 0]。
数组之和为 0，可以被 6 整除。

说明：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• 1 <= k <= 100

思路

返回数组元素和模 k 的余数。

代码

/**
 * @date 2025-11-29 21:53
 */
public class MinOperations3512 {

    public int minOperations(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum % k;
    }
}

性能

目标

给定一个二进制数组 nums ( 索引从0开始 )。

我们将 xi 定义为其二进制表示形式为子数组 nums[0..i] (从最高有效位到最低有效位)。

• 例如，如果 nums =[1,0,1] ，那么 x0 = 1, x1 = 2, 和 x2 = 5。

返回布尔值列表 answer，只有当 xi 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

示例 1：

输入：nums = [0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为 true 。

示例 2：

输入：nums = [1,1,1]
输出：[false,false,false]

说明：

• 1 <= nums.length <= 10^5
• nums[i] 仅为 0 或 1

思路

有一个二进制数组 nums，定义 xi 为二进制表示为 子数组 [0, i] 的数字，判断 x0 ~ x_(n-1) 能否被 5 整除。

模拟存在的问题是左移多次会溢出。假设 num = k * 5 + mod，左移 1 位相当于乘以 2，2 * num = k * 10 + 2 * mod，能否被 5 整除只需考虑 2 * mod | nums[i]。

代码

/**
 * @date 2025-11-24 8:52
 */
public class PrefixesDivBy5_1018 {

    public List<Boolean> prefixesDivBy5_v1(int[] nums) {
        List<Boolean> res = new ArrayList<>();
        int mod = 0;
        for (int num : nums) {
            mod = (mod << 1) % 5 + num;
            res.add(mod % 5 == 0);
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums 。一次操作中，你可以将 nums 中的 任意 一个元素增加或者减少 1 。

请你返回将 nums 中所有元素都可以被 3 整除的 最少 操作次数。

示例 1：

输入：nums = [1,2,3,4]
输出：3
解释：
通过以下 3 个操作，数组中的所有元素都可以被 3 整除：
将 1 减少 1 。
将 2 增加 1 。
将 4 减少 1 。

示例 2：

输入：nums = [3,6,9]
输出：0

说明：

1 <= nums.length <= 50
1 <= nums[i] <= 50

思路

统计数组中不能被 3 整除的元素个数。

代码

/**
 * @date 2025-11-22 2:02
 */
public class MinimumOperations3190 {

    public int minimumOperations(int[] nums) {
        int res = 0;
        for (int num : nums) {
            if (num % 3 != 0){
                res++;
            }
        }
        return res;
    }
}

性能