2026-10-04最大有效数对和。用go语言给定一个包含 n 个整数的数组 nums以及一个整数 k。选取两个索引 i 和 j要求 i 位于 j 的左侧并且两个索引之间的差值不小于 k也就是 j 减去 i 的结果至少为 k。对于所有满足这种要求的索引组合计算 nums[i] 与 nums[j] 的和最后返回这些和当中最大的那个值。2 n nums.length 100000。1 nums[i] 1000000000。1 k n - 1。输入 nums [1,3,5,2,8], k 2。输出 13。解释有效对为(0, 2): nums[0] nums[2] 6(0, 3): nums[0] nums[3] 3(0, 4): nums[0] nums[4] 9(1, 3): nums[1] nums[3] 5(1, 4): nums[1] nums[4] 11(2, 4): nums[2] nums[4] 13因此答案为 13 。题目来自力扣3979。具体过程可以分步骤理解初始化答案和左侧最大值用 ans 保存目前找到的最大有效数对和初始为 0。用 mx 保存当前所有合法左端点中的最大值初始也为 0。由于题目中 nums[i] 都是正数初始为 0 不会影响最终结果。右端点从 k 开始遍历因为要求 j - i k且 i 必须小于 j所以最小的右端点 j 至少是 k。因此循环让 j 从 k 一直走到数组最后一个位置。每次先扩大合法左端点范围当右端点移动到 j 时新变得合法的左端点是 j-k。也就是说之前 j 较小时位置 j-k 还不能作为左端点现在 j 增大了位置 j-k 满足 j - (j-k) k所以它可以被选为左端点了。于是把 nums[j-k] 纳入考虑范围并更新 mxmx 变成原来的 mx 和 nums[j-k] 中较大的那个。更新后mx 就代表从下标 0 到 j-k 这个范围内所有 nums[i] 的最大值。计算以当前 j 为右端点的最佳和当前右端点是 nums[j]左端点只需要选合法的最大值 mx。所以以 j 为右端点时最佳有效数对和就是 mx nums[j]。然后用这个和去更新全局答案 ans使 ans 始终保存目前遇到的最大值。遍历结束后返回 ans因为每个右端点 j 都计算了它对应的最佳左端点组合所以最终 ans 就是所有合法数对和中的最大值。以示例 nums [1, 3, 5, 2, 8]k 2 为例初始 ans 0mx 0。j 2把 nums[0] 1 纳入左端点候选mx 1。当前右端点是 nums[2] 5候选和为 1 5 6ans 6。j 3把 nums[1] 3 纳入左端点候选mx max(1, 3) 3。当前右端点是 nums[3] 2候选和为 3 2 5ans 仍为 6。j 4把 nums[2] 5 纳入左端点候选mx max(3, 5) 5。当前右端点是 nums[4] 8候选和为 5 8 13ans 更新为 13。循环结束返回 13。这个方法之所以正确是因为对于每一个右端点 j它都只关心合法左端点范围内最大的那个值。而随着 j 不断向右移动合法左端点范围只会扩大不会缩小所以可以用一个变量 mx 动态维护这个范围内的最大值不需要每次重新扫描。总的时间复杂度只对右端点 j 从 k 到 n-1 遍历一次每次只做常数次比较和加法因此时间复杂度是 O(n)。总的额外空间复杂度只使用了 ans、mx 等常数个变量没有额外开辟与数组规模相关的空间因此额外空间复杂度是 O(1)。如果算输入数组本身总空间是 O(n)但额外空间是 O(1)。Go完整代码如下packagemainimport(fmt)funcmaxValidPairSum(nums[]int,kint)(ansint){mx:0forj:k;jlen(nums);j{mxmax(mx,nums[j-k])// nums[i] 的最大值ansmax(ans,mxnums[j])}return}funcmain(){nums:[]int{1,3,5,2,8}k:2result:maxValidPairSum(nums,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defmax_valid_pair_sum(nums,k):ans0mx0forjinrange(k,len(nums)):mxmax(mx,nums[j-k])# nums[i] 的最大值ansmax(ans,mxnums[j])returnansif__name____main__:nums[1,3,5,2,8]k2resultmax_valid_pair_sum(nums,k)print(result)C完整代码如下#includeiostream#includevector#includealgorithmintmaxValidPairSum(conststd::vectorintnums,intk){intans0;intmx0;intnstatic_castint(nums.size());for(intjk;jn;j){mxstd::max(mx,nums[j-k]);// nums[i] 的最大值ansstd::max(ans,mxnums[j]);}returnans;}intmain(){std::vectorintnums{1,3,5,2,8};intk2;intresultmaxValidPairSum(nums,k);std::coutresultstd::endl;return0;}
