2026-08-07：移除子数组元素后第 K 小偶数。用go语言，给定一个严格递增的整数数组 nums，以及一组查询，每个查询包含三个整数 l、r 和 k。

对于每个查询，我们只看 nums 中下标从 l 到 r 的这一段连续子数组。

接着，考虑所有正偶数组成的无限序列：2, 4, 6, 8, 10, …

从这个序列中，剔除掉那些正好等于上述子数组里出现的数值的元素。

剔除之后，序列仍然保持从小到大排列，我们需要找出这个新序列中的第 k 个最小的整数。

最后，将每个查询对应的第 k 个最小整数按顺序放入结果数组中返回。

注意：nums 本身是严格递增的，所以任意子数组中的元素也是严格递增且互不相同的。

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000000。

nums 是严格递增的。

1 <= queries.length <= 100000。

queries[i] = [li, ri, ki]。

0 <= li <= ri < nums.length。

1 <= ki <= 1000000000。

输入： nums = [1,4,7], queries = [[0,2,1],[1,1,2],[0,0,3]]。

输出： [2,6,6]。

解释：

因此，ans = [2, 6, 6]。

题目来自力扣3911。

算法总体思路

本题要求对每个查询，在全局正偶数序列（2, 4, 6, …）中删除指定子数组里出现的偶数后，找出第 k 个剩下的偶数。
由于nums本身严格递增，子数组中的偶数也是严格递增且互不重复，因此我们可以利用“删除偶数在原偶数序列中的序号”来快速定位。

核心思想：
将每个偶数v映射为其在偶数序列中的序号v / 2（从 1 开始）。
对于某个查询，子数组中所有偶数对应的序号构成一个严格递增的集合S（记为被删除的序号）。
我们要求在删除S后，剩下的序号中第k个最小的序号t，然后答案就是2 * t。

预处理

1. 遍历整个nums，找出所有值为偶数的元素，并记录它们的原始下标，存入数组evenPos。
   • 因为nums严格递增，所以evenPos中的下标也是严格递增的。
   • 这一步耗时 O(n)，n 为nums长度。

每个查询的处理步骤

对于每个查询[l, r, k]，我们按如下过程计算答案：

1. 定位子数组内所有偶数下标

• 在evenPos中，使用二分查找找到第一个≥ l的位置left。
• 再找到第一个≥ r+1的位置right（由于r是闭区间，r+1作为开区间右边界）。
• 则evenPos[left : right]就是所有落在[l, r]区间内的偶数下标，记为数组pos，其长度为m。
  • 若m = 0，说明子数组中没有偶数，删除集合为空，那么第k个剩余偶数就是整个偶数序列的第k个，即2 * k。

2. 将子数组偶数映射为序号并理解删除影响

• 对于pos中的第j个元素（0 ≤ j < m），其对应的偶数值为nums[pos[j]]，该偶数在全局偶数序列中的序号为nums[pos[j]] / 2。
• 在考虑这个偶数之前，全局序号小于它的偶数共有nums[pos[j]] / 2 - 1个。
• 由于pos[0..j-1]都是比它更小的被删除偶数（共j个），所以在所有小于该偶数的偶数中，被删除的个数正好是j。
• 因此，在该偶数之前（不包括它本身）剩余的偶数个数为：
  剩余个数 = (nums[pos[j]] / 2 - 1) - j。

3. 二分查找第k个剩余偶数落在哪个区间

• 我们需要在所有被删除偶数（共m个）中找到“分界点”。
• 定义函数f(j)（其中0 ≤ j ≤ m）：
  • 当j = m时，表示所有被删除偶数都已考虑完毕，此时可以认为f(m) = true（即第k个剩余偶数一定在所有被删除偶数之后）。
  • 当0 ≤ j < m时，f(j) = ( (nums[pos[j]] / 2 - 1 - j) ≥ k )。
• 由于nums严格递增且偶数至少增加 2，可证明f(j)的值随着j增大从false单调变为true。因此可以在[0, m]上进行二分查找，找到最小的j使得f(j)成立。

4. 根据分界点计算答案

• 找到的j表示：在前j个被删除偶数之前，已经有至少k个剩余偶数；但在前j-1个之前不够。
• 因此，第k个剩余偶数一定位于第j-1个被删除偶数之后、第j个被删除偶数之前（若j=0，则在第一个被删除偶数之前；若j=m，则在所有被删除偶数之后）。
• 此时，在所有小于该答案的偶数中，恰好有j个被删除（即pos[0..j-1]），所以该答案在原始偶数序列中的序号为j + k。
• 最终答案为(j + k) * 2。

为什么二分条件正确

• 如果f(j)为真，说明在第j个被删除偶数之前，剩余的偶数个数已经不少于k，那么第k个剩余偶数不可能在第j个被删除偶数之后，答案的序号小于等于nums[pos[j]] / 2（但不会等于它，因为该值已被删除），因此我们可以把搜索范围向左收缩。
• 如果f(j)为假，则说明前面剩余个数不足k，答案必然在第j个被删除偶数之后，搜索范围向右移动。
• 二分查找最终确定分界点，使计算准确。

时间复杂度

• 预处理：遍历一次nums，O(n)，n 为nums长度。
• 每个查询需要三次二分查找：
  1. 在evenPos中找left，O(log n)；
  2. 找right，O(log n)；
  3. 在pos上二分，O(log m) ≤ O(log n)。
• 总查询数为 q，所以总时间复杂度为O(n + q log n)。

额外空间复杂度

• 存储evenPos数组，最多 O(n)。
• 存储答案数组，O(q)。
• 其他临时变量 O(1)。
• 因此总额外空间复杂度为O(n + q)。

最终回答示例

对于题中示例nums = [1,4,7]，queries = [[0,2,1],[1,1,2],[0,0,3]]，过程可归纳为：

• 预处理的evenPos = [1]（只有下标 1 的 4 是偶数）。
• 查询 0：子数组[1,4,7]，pos = [1]，m=1，二分得到j=0（因为4/2-1-0 = 1 ≥ 1），答案(0+1)*2=2。
• 查询 1：子数组[4]，同样pos=[1]，k=2，f(0)=1-0=1 < 2，f(1)=true（j=m），所以j=1，答案(1+2)*2=6。
• 查询 2：子数组[1]，无偶数，pos=[]，m=0，二分返回j=0，答案(0+3)*2=6。
  结果[2,6,6]，与预期一致。

Go完整代码如下：

packagemainimport("fmt""sort")funckthRemainingInteger(nums[]int,queries[][]int)[]int{// 记录所有偶数的下标evenPos:=[]int{}fori,x:=rangenums{ifx%2==0{evenPos=append(evenPos,i)}}ans:=make([]int,len(queries))fori,q:=rangequeries{// 找到询问对应的 evenPos 的子数组l:=sort.SearchInts(evenPos,q[0])r:=sort.SearchInts(evenPos,q[1]+1)pos:=evenPos[l:r]k:=q[2]// 推导过程见 1539 题解j:=sort.Search(len(pos),func(jint)bool{returnnums[pos[j]]/2-1-j>=k})ans[i]=(j+k)*2}returnans}funcmain(){nums:=[]int{1,4,7}queries:=[][]int{{0,2,1},{1,1,2},{0,0,3}}result:=kthRemainingInteger(nums,queries)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-importbisectdefkthRemainingInteger(nums,queries):# 收集 nums 中所有偶数元素的下标（因为 nums 严格递增，下标也是递增的）even_pos=[ifori,xinenumerate(nums)ifx%2==0]ans=[]forl,r,kinqueries:# 在 even_pos 中定位落在 [l, r] 区间内的下标范围left=bisect.bisect_left(even_pos,l)right=bisect.bisect_right(even_pos,r)pos=even_pos[left:right]# 这些下标对应的 nums 值都是偶数，且在子数组内# 二分查找最小的 j，使得 nums[pos[j]]//2 - 1 - j >= klo,hi=0,len(pos)whilelo<hi:mid=(lo+hi)//2# 当前偶数在原始偶数序列中的序号（从0开始）减去前面已移除的偶数个数ifnums[pos[mid]]//2-1-mid>=k:hi=midelse:lo=mid+1j=lo# 第 k 个剩余偶数的原始序号为 j + k，数值为 (j + k) * 2ans.append((j+k)*2)returnansdefmain():nums=[1,4,7]queries=[[0,2,1],[1,1,2],[0,0,3]]result=kthRemainingInteger(nums,queries)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;vector<int>kthRemainingInteger(vector<int>&nums,vector<vector<int>>&queries){vector<int>evenPos;// 收集 nums 中所有偶数元素的下标for(inti=0;i<(int)nums.size();++i){if(nums[i]%2==0){evenPos.push_back(i);}}vector<int>ans;ans.reserve(queries.size());for(auto&q:queries){intl=q[0],r=q[1],k=q[2];// 在 evenPos 中定位属于 [l, r] 的下标范围intleftIdx=lower_bound(evenPos.begin(),evenPos.end(),l)-evenPos.begin();intrightIdx=lower_bound(evenPos.begin(),evenPos.end(),r+1)-evenPos.begin();intm=rightIdx-leftIdx;// 该区间内偶数的个数// 二分查找最小的 j，使得 nums[evenPos[leftIdx + j]] / 2 - 1 - j >= kintlo=0,hi=m;while(lo<hi){intmid=(lo+hi)/2;intidx=evenPos[leftIdx+mid];if(nums[idx]/2-1-mid>=k){hi=mid;}else{lo=mid+1;}}intj=lo;ans.push_back((j+k)*2);}returnans;}intmain(){vector<int>nums={1,4,7};vector<vector<int>>queries={{0,2,1},{1,1,2},{0,0,3}};vector<int>result=kthRemainingInteger(nums,queries);for(intx:result){cout<<x<<" ";}cout<<endl;return0;}