leetcode周赛(195)
问题一：检查数组对是否可以被k整除
问题描述：
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 True ；否则，返回 False 。
示例 1：
输入：arr = [1,2,3,4,5,10,6,7,8,9], k = 5
输出：true
解释：划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10) 。
示例 2：
输入：arr = [1,2,3,4,5,6], k = 7
输出：true
解释：划分后的数字对为 (1,6),(2,5) 以及 (3,4) 。
示例 3：
输入：arr = [1,2,3,4,5,6], k = 10
输出：false
解释：无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。
示例 4：
输入：arr = [-10,10], k = 2
输出：true
示例 5：
输入：arr = [-1,1,-2,2,-3,3,-4,4], k = 3
输出：true
arr.length == n
1 <= n <= 10^5
n 为偶数
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-if-array-pairs-are-divisible-by-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。大体思路
看到题的初步的思路是：两层循环，每个元素依次与其他元素见面，从而判断能否组成的数对被k整除。但是发现1 <= n <= 10^5，O（N^2）时间复杂度的肯定过不去。
若(a + b) % k == 0 则存在以下三种情况 ：
a % k + b % k = 0;
a % k + b % k = k;
a % k + b % k = -k;(由于arr中存在负数)
因此我们可以使用一Map存储将其余数及其出现的次数，最终利用上述三个等式进行”开心消消乐”，最终Map为空则证明由其划分的数组对可以被k整除。编码时为了节省遍历次数，使用边统计边消除的方式一次遍历即可完成。实现代码如下：
class Solution {
public boolean canArrange(int[] arr, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int item : arr){
int remainder = item % k;
if(map.getOrDefault(0 - remainder, 0) > 0){
map.put(0 - remainder, map.get(0 - remainder) - 1);
}else if(map.getOrDefault(k - remainder, 0) > 0){
map.put(k - remainder, map.get(k - remainder) - 1);
}else if(map.getOrDefault(-k - remainder, 0) > 0){
map.put(-k - remainder, map.get(-k - remainder) - 1);
}else{
map.put(remainder, map.getOrDefault(remainder, 0) + 1);
}
}
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
if(entry.getValue() > 0){
return false;
}
}
return true;
}
} 该解决方案时间复杂度O（N），额外空间复杂度O（N）
问题二：满足条件的子序列数目
问题描述：
给你一个整数数组 nums 和一个整数 target 。
请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
由于答案可能很大，请将结果对 10^9 + 7 取余后返回。
示例 1：
输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)
示例 2：
输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
示例 3：
输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）
示例 4：
输入：nums = [5,2,4,1,7,6,8], target = 16
输出：127
解释：所有非空子序列都满足条件 (2^7 - 1) = 127
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。大体思路
当时做的时候没注意子序列，当子串处理了，一直还在想用维持最大值最小值的滑动窗口处理。
对于该子序列问题，可以先排序，然后从使用双指针的方式，依次得到包含nums[i]的满足条件的子序列数目，最终把这些数目一加即可。
具体做法为使用一left指针（初始指向最左端）、一right指针（初始指向最右端）。判断此时的sum和target的关系。其中sum = nums[left] + nums[right];
若 sum <= target 则证明nums[left] 和 left + 1 到 right任意元素均可以得到满足条件的子序列。子序列的数量等于 2^(right - left) ( 由于从left + 1 到 right 一共right-left个元素，对于每个元素有选或不选两种状态，因此组合后为 2 ^ (right - left)) 。
若 sum >= target right–；
此外由于1 <= nums.length <= 10^5，2的10^5包溢出的。题目说为了避免溢出结果对10^9 + 7 取余。
因此我们只想要其的余数，并不关心其本身的值。使用快速幂求解，定义一int型的pows数组。
其中pows[i]为 2 ^ i % (10^9 + 7)。其中pows[i] = (2 * pows[i - 1] )% k。
实现代码如下：
class Solution {
public int numSubseq(int[] nums, int target) {
Arrays.sort(nums);
int[] pows = new int[nums.length];
pows[0] = 1;
int mod = (int)Math.pow(10, 9) + 7;
for(int i = 1; i < pows.length; i++){
pows[i] = (pows[i - 1] * 2) % mod;
}
int left = 0, right = nums.length - 1;
int result = 0;
while(left <= right){
if(nums[left] + nums[right] > target){
right--;
}else{
result = (result + pows[right - left]) % mod;
left++;
}
}
return result;
}
} 该方案由于right总是往左走，left总是往右走，时间复杂度为O（N），由于需要存储pows，额外空间复杂度为O（N）。
我们发现在以nums[left]开头时寻找满足sum <= target最右边的right时right是一步一步往左走的，又该序列由是递增的因此可以采用二分查找来找到需要的right。可以将该步的时间复杂度度降为O（logN），但是由于需要算快速幂，总体时间复杂度依然为O（N）。优化后的代码如下 ：
class Solution {
public int numSubseq(int[] nums, int target) {
Arrays.sort(nums);
int[] pows = new int[nums.length];
pows[0] = 1;
int mod = (int)Math.pow(10, 9) + 7;
for(int i = 1; i < pows.length; i++){
pows[i] = (pows[i - 1] * 2) % mod;
}
int left = 0, right = nums.length - 1;
int result = 0;
while(left <= right){
int temp = searchLast(nums, left, right, target - nums[left]);
if(temp == -1){
break;
}
result = (result + pows[temp - left]) % mod;
left++;
right = temp;
}
return result;
}
// 找到小于等于target的最后一个元素
public int searchLast(int[] nums, int left, int right, int target){
while(left < right - 1){
int mid = left + (right - left) / 2;
if(nums[mid] > target){
right = mid;
}else{
left = mid;
}
}
if(nums[right] <= target){
return right;
}else if(nums[left] <= target){
return left;
}
return -1;
}
}腾讯云开发者
