MarsCode青训营打卡Day5（2025年1月18日）|稀土掘金-148.小A的子数组权值、304.计算特定条件下的四元组数量
资源引用：
148.小A的子数组权值
304.计算特定条件下的四元组数量
今日小记：
148.题既可以如笔者给出的题解来遍历全部的子数组，也可以按照遍历权值的方式通过滑动窗口来实现，两种解题方法的时间复杂度相同，但前者的操作更为简单。
304.题与Day4的三元组一题有相似之处，均通过将多元组拆分成更小的元组再进行计算，从而简化了计算。
稀土掘金-148.小A的子数组权值（148.小A的子数组权值）
题目分析：
给定一个长度为n的数组a，定义“权值”为一个连续子数组内不同元素的个数。
求该数组中权值为1,2,3...,n的连续子数组数量有多少个，通过输出一个包含n个整数的，第i个数表示权值为i的子数组个数的数组来作答。
解题重点：
由于题目限定了“连续子数组”的“连续”，故考虑用双指针实现的增广窗口来遍历所有连续子数组。
又因为需要知道连续子数组中不同元素的个数，因此我们可以为每个增广窗口配套一个哈希表以记录当前连续子数组所包含的不同元素，而keySet的长度就是该子数组的权值。
import java.util.Arrays;
import java.util.Set;
import java.util.HashSet;
public class Main {
public static int[] solution(int n, int[] a) {
int[] c = new int[n + 1];
for (int left = 0; left < n; left++) {
Set<Integer> set = new HashSet<>();
for (int right = left; right < n; right++) {
set.add(a[right]);
c[set.size()]++;
}
}
return Arrays.copyOfRange(c, 1, c.length);
}
public static void main(String[] args) {
System.out.println(Arrays.equals(solution(4, new int[]{1, 2, 2, 3}), new int[]{5, 4, 1, 0}));
System.out.println(Arrays.equals(solution(3, new int[]{1, 1, 1}), new int[]{6, 0, 0}));
System.out.println(Arrays.equals(solution(5, new int[]{1, 2, 3, 2, 1}), new int[]{5, 5, 5, 0, 0}));
}
}稀土掘金-304.计算特定条件下的四元组数量（304.计算特定条件下的四元组数量）
题目分析：
给定一个长度为n的数组a，要求计算有多少个四元组(i, j, k, l)满足以下条件：
- i < j < k < l
- a_i + a_j == a_k ^ a_l
此外，由于计算过程中的数可能非常大，需要对计算结果取10^9 + 7的模后输出结果。
解题重点：
该四元组由两部分构成，即相加的部分和异或的部分，故可分为两个二元组来考虑。
又因为计算过程中，使用元素值进行计算，对下标有相对关系的要求，我们可以考虑用哈希映射，将元素值和对应下标构造成键值对，分别将两个二元组的运算结果及下标存储到两个Map中。并且，由于在相加二元组中，i<j；在异或二元组中，k<l；两个二元组之间，只需满足j<k即可，故两个Map的键值对的值只需分别存储 j 和 k 即可。注意：由于不同的二元组的计算结果可能相同，故相同键可以有多个不同的值，用List存储
还需注意，在计算过程中时刻需要对 10^9 + 7取模（在实际计算中使用1000000007L表示），为防止数值溢出，计算过程中用长整型long做运算，最终转回int并返回。
解题思路：
- 构造HashMap<Long, List<Integer>> map1, map2。初始化返回值res
- 遍历数组a，将i < j的二元组(i, j)的元素和a_i + a_j （模后）作为键、j作为值，存储至map1
- 遍历数组a，将k < l的二元组(k, l)的元素和a_k ^ a_l （模后）作为键，k作为值，存储值map2
- 遍历map1的键key，在map2中查询是否存在key，若存在，判断 j < k是否成立，若成立，则res++。
- 最终返回res（模后）。
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
public class Main {
private static final long MOD = 1000000007L;
public static int solution(int n, int[] a) {
long res = 0;
Map<Long, List<Integer>> map1 = new HashMap<>();
Map<Long, List<Integer>> map2 = new HashMap<>();
/*1.构造相加二元组的HashMap */
for (int i = 0; i < a.length - 3; i++) {
for (int j = i + 1; j < a.length - 2; j++) {
long sum = (a[i] + a[j]) % MOD;
map1.computeIfAbsent(sum, K -> new ArrayList<>()).add(j);
}
}
/*2.构造异或二元组的HashMap */
for (int k = 2; k < a.length; k++) {
for (int l = k + 1; l < a.length; l++) {
long xor = (a[k] ^ a[l]) % MOD;
map2.computeIfAbsent(xor, K -> new ArrayList<>()).add(k);
}
}
/*3.遍历map1的键，在map2中查询key，并比较二者的value，得到符合条件的四元组个数 */
for (long key : map1.keySet()) {
if (!map2.containsKey(key)) continue;
List<Integer> list1 = map1.get(key);
List<Integer> list2 = map2.get(key);
for (int value1 : list1) {
for (int value2 : list2) {
if (value1 < value2) res = (res + 1) % MOD;
}
}
}
return (int)res;
}
public static void main(String[] args) {
System.out.println(solution(5, new int[]{2, 3, 1, 5, 4}) == 1);
System.out.println(solution(6, new int[]{1, 2, 3, 4, 5, 6}) == 1);
System.out.println(solution(4, new int[]{4, 1, 3, 2}) == 0);
}
}总结反思：
- 对1000000007L取模是一种常见的防溢出技巧
- 使用类接口实现的具体对象时，必须谨记ta是一个实体，ta作为参数时实际上使用的是ta的引用。在笔者原先的代码中，错误的将唯一的实例tmpList作为参数传递给map后，直接将其复用或清空，都导致了数据的丢失。
- map.computerIfAbsent的使用方式：在map中查询key是否存在，若存在返回其值，否则调用mappingFunction计算值。
V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)