第二题没认真读题，是三数之和，不是三数的积
2176. 统计数组中相等且可以被整除的数对
给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ，请你返回满足 0 <= i < j < n ，nums[i] == nums[j] 且 (i j) 能被 k 整除的数对 (i, j) 的 *数目 。
示例 1：
输入：nums = [3,1,2,2,2,1,3], k = 2 输出：4 解释： 总共有 4 对数符合所有要求： - nums[0] == nums[6] 且 0 6 == 0 ，能被 2 整除。 - nums[2] == nums[3] 且 2 3 == 6 ，能被 2 整除。 - nums[2] == nums[4] 且 2 4 == 8 ，能被 2 整除。 - nums[3] == nums[4] 且 3 4 == 12 ，能被 2 整除。
示例 2：
输入：nums = [1,2,3,4], k = 1 输出：0 解释：由于数组中没有重复数值，所以没有数对 (i,j) 符合所有要求。
提示：
- 1 <= nums.length <= 100
- 1 <= nums[i], k <= 100
思路：
暴力枚举即可
class Solution {public int countPairs(int[] nums, int k) {int cnt = 0 ;for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[i] == nums[j] && (i * j) % k == 0)cnt++;}}return cnt;}}
2177. 找到和为给定整数的三个连续整数
给你一个整数 num ，请你返回三个连续的整数，它们的 和 为_ _num 。如果 num 无法被表示成三个连续整数的和，请你返回一个 空 数组。
示例 1：
输入：num = 33 输出：[10,11,12] 解释：33 可以表示为 10 + 11 + 12 = 33 。 10, 11, 12 是 3 个连续整数，所以返回 [10, 11, 12] 。
示例 2：
输入：num = 4 输出：[] 解释：没有办法将 4 表示成 3 个连续整数的和。
提示：
- 0 <= num <= 1015
思路：
三个连续的数的和一定能被3整除，故给定的num如果不能被3整除，返回空数组，否则返回num / 3 - 1, num / 3, num / 3 +
class Solution {public long[] sumOfThree(long num) {if (num % 3 != 0)return new long[]{};long x = num / 3;return new long[]{x - 1, x, x + 1};}}
2178. 拆分成最多数目的正偶数之和
给你一个整数 finalSum 。请你将它拆分成若干个 互不相同 的正偶数之和，且拆分出来的正偶数数目 最多 。
- 比方说，给你 finalSum = 12 ，那么这些拆分是 符合要求 的（互不相同的正偶数且和为 finalSum）：(2 + 10) ，(2 + 4 + 6) 和 (4 + 8) 。它们中，(2 + 4 + 6) 包含最多数目的整数。注意 finalSum 不能拆分成 (2 + 2 + 4 + 4) ，因为拆分出来的整数必须互不相同。
请你返回一个整数数组，表示将整数拆分成 最多 数目的正偶数数组。如果没有办法将 finalSum 进行拆分，请你返回一个 空 数组。你可以按 任意 顺序返回这些整数。
示例 1：
输入：finalSum = 12 输出：[2,4,6] 解释：以下是一些符合要求的拆分：(2 + 10)，(2 + 4 + 6) 和 (4 + 8) 。 (2 + 4 + 6) 为最多数目的整数，数目为 3 ，所以我们返回 [2,4,6] 。 [2,6,4] ，[6,2,4] 等等也都是可行的解。
示例 2：
输入：finalSum = 7 输出：[] 解释：没有办法将 finalSum 进行拆分。 所以返回空数组。
示例 3：
输入：finalSum = 28 输出：[6,8,2,12] 解释：以下是一些符合要求的拆分：(2 + 26)，(6 + 8 + 2 + 12) 和 (4 + 24) 。 (6 + 8 + 2 + 12) 有最多数目的整数，数目为 4 ，所以我们返回 [6,8,2,12] 。 [10,2,4,12] ，[6,2,4,16] 等等也都是可行的解。
提示：
- 1 <= finalSum <= 1010
思路：
奇数无论怎么分不行，返回0即可
贪心，从2开始枚举，对目标数进行拆分。
若枚举到x是目标数剩余值y小于x，y已经被枚举过，考虑将y与x组合构成最后一个数，并删除之前枚举过的y即可。
class Solution {public List<Long> maximumEvenSplit(long finalSum) {if (finalSum % 2 != 0) return new ArrayList<Long>();List<Long> list = new ArrayList<>();long x = 2;while (finalSum >= x) {list.add(x);finalSum -= x;x += 2;}if (finalSum == 0)return list;int idx = 0;while (finalSum + list.get(idx) != x) idx++;list.set(idx, x);return list;}}
2179. 统计数组中好三元组数目
给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, …, n - 1] 的 排列 。
好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。
请你返回好三元组的 总数目 。
示例 1：
输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3] 输出：1 解释： 总共有 4 个三元组 (x,y,z) 满足 pos1x < pos1y < pos1z ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。 这些三元组中，只有 (0,1,3) 满足 pos2x < pos2y < pos2z 。所以只有 1 个好三元组。
示例 2：
输入：nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3] 输出：4 解释：总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。
提示：
- n == nums1.length == nums2.length
- 3 <= n <= 105
- 0 <= nums1[i], nums2[i] <= n - 1
- nums1 和 nums2 是 [0, 1, …, n - 1] 的排列。
思路：
两个数组都是乱序的，考虑将一个数组中的数字变为有序，由于两个数组中的数字一一对应，故可以将第二个数组中每一个数进行映射使其有序。然后将第一个数组中的每个数按相同的规则进行映射。统计递增三元组的数量即可，用树状数组。
class Solution {public long goodTriplets(int[] nums1, int[] nums2) {int n = nums1.length;int[] a = new int[n];int[] b = new int[n];for (int i = 0; i < n; i++) {a[nums2[i]] = i; // 映射}for (int i = 0; i < n; i++) {b[i] = a[nums1[i]] + 1;}long res = 0;BIT bit = new BIT(n);for (int i = 0; i < n; i++) {int x = b[i];res += 1L * bit.sum(x - 1) * (n - x - (bit.sum(n) - bit.sum(x)));bit.add(x, 1);}return res;}class BIT {int[] a;int n;BIT(int n) {this.n = n;a = new int[n + 1];}int sum(int idx) {int res = 0;for (int i = idx; i > 0; i -= i & (-i))res += a[i];return res;}void add(int idx, int x) {for (int i = idx; i <= n; i += i & (-i))a[i] += x;}}}
:::tips 两维无序，考虑将一维变有序 :::
若有收获，就点个赞吧
0 人点赞
