欢迎大家加QQ群：623375442，可以方便群里面交流。
100285. Find the Integer Added to Array I
给你两个长度相等的数组 nums1 和 nums2。
数组 nums1 中的每个元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。
在与 x 相加后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。
返回整数 x 。
测试样例：
输入：nums1 = [2,6,4], nums2 = [9,7,5]
输出：3
解释：与 3 相加后，nums1 和 nums2 相等。
解答：测试用例以这样的方式生成：存在一个整数 x，使得 nums1 中的每个元素都与 x 相加后，nums1 与 nums2 相等。所以排序之后，各个位置对应的差一定相同。那么寻找一下最小值，做个diff就OK了。
class Solution {
public int addedInteger(int[] nums1, int[] nums2) {
int m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE;
for (int n : nums1) {
m1 = Math.min(m1, n);
}
for (int n : nums2) {
m2 = Math.min(m2, n);
}
return m2 - m1;
}
}100287. Find the Integer Added to Array II
给你两个整数数组 nums1 和 nums2。
从 nums1 中移除两个元素，并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。
执行上述操作后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。
返回能够实现数组相等的 最小 整数 x 。
测试样例：
输入：nums1 = [4,20,16,12,8], nums2 = [14,18,10]
输出：-2
解释：移除 nums1 中下标为 [0,4] 的两个元素，并且每个元素与 -2 相加后，nums1 变为 [18,14,10] ，与 nums2 相等。
解答：这题范围太小了，3 <= nums1.length <= 200。直接暴力也没啥问题。和第一题差不多思路，排序之后暴力枚举所有可能。
class Solution {
public int minimumAddedInteger(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int res = Integer.MAX_VALUE;
for (int i = 0; i < nums1.length; ++i) {
for (int j = i + 1; j < nums1.length; ++j) {
int p = 0, diff = Integer.MIN_VALUE;
boolean isValid = true;
for (int n : nums2) {
while (p == i || p == j) {
++p;
}
if (diff == Integer.MIN_VALUE) {
diff = n - nums1[p];
} else if (n - nums1[p] != diff) {
isValid = false;
break;
}
++p;
}
if (isValid) {
res = Math.min(res, diff);
}
}
}
return res;
}
}100282. Minimum Array End
给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。
返回 nums[n - 1] 可能的 最小 值。
测试样例：
输入：n = 3, x = 4
输出：6
解释：数组 nums 可以是 [4,5,6] ，最后一个元素为 6 。
解答：稍微有点脑经急转弯。因为满足 nums[i + 1] 大于 nums[i]，又因为AND运算之后要是x，那么所有x对应的二进制位都必须为1.那就是在剩下是0的位上寻找第n大的数。跳过1位，把n分散到0位就OK了。
class Solution {
public long minEnd(int n, int x) {
long res = 0;
int offset = 0;
--n;
for (int i = 0; i < 63; ++i) {
// 如果当前为对于x不是1位，我们寻找第N大的数字
if (!isMark(x, i)) {
// 逻辑比较简单，如果当前位是1，就赋值
if (isMark(n, offset)) {
res += (1L << i);
}
++offset;
} else {
res += (1L << i);
}
}
return res;
}
private static boolean isMark(long num, int offset) {
long t = (num >> offset) & 1;
return t == 1;
}
}100257. Find the Median of the Uniqueness Array
给你一个整数数组 nums 。数组 nums 的 唯一性数组 是一个按元素从小到大排序的数组，包含了 nums 的所有非空子数组中不同元素的个数。
换句话说，这是由所有 0 <= i <= j < nums.length 的 distinct(nums[i..j]) 组成的递增数组。
其中，distinct(nums[i..j]) 表示从下标 i 到下标 j 的子数组中不同元素的数量。
返回 nums 唯一性数组 的 中位数 。
注意，数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。
测试样例：
输入：nums = [1,2,3]
输出：1
解释：nums 的唯一性数组为 [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])]，即 [1, 1, 1, 2, 2, 3] 。唯一性数组的中位数为 1 ，因此答案是 1 。
解答：这周这题，难度没7分。外层一个折半搜索。内层利用双指针就能计算出distinct小于mid时，所有出现的次数。
class Solution {
public int medianOfUniquenessArray(int[] nums) {
int st = 1, ed = nums.length;
long total = (1L + nums.length) * nums.length / 2;
long target = total / 2 + total % 2;
// 外层的重点在于折半，设定的distinct数量越多，那么满足要求字数组数量就越多
while (st < ed) {
int mid = (st + ed) / 2;
long c = countExist(nums, mid);
if (c < target) {
st = mid + 1;
} else {
ed = mid;
}
}
return st;
}
private long countExist(int[] nums, int mid) {
int st = 0, ed = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(nums[0], 1);
long res = 0;
// 利用双指针计算负荷要求的数组长度，并计算满足要求的子数组数量。
while (st < nums.length) {
while (ed < nums.length && map.size() <= mid) {
++ed;
if (ed < nums.length) {
map.put(nums[ed], map.getOrDefault(nums[ed], 0) + 1);
}
}
res += (ed - st);
int oldCount = map.get(nums[st]);
if (oldCount == 1) {
map.remove(nums[st]);
} else {
map.put(nums[st], oldCount - 1);
}
++st;
}
return res;
}
}