2026-10-04：最大有效数对和。用go语言，给定一个包含 n 个整数的数组 nums，以及一个整数 k。选取两个索引 i 和 j，要求 i 位于 j 的左

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。

具体过程可以分步骤理解：

1. 1. 初始化答案和左侧最大值
   用 ans 保存目前找到的最大有效数对和，初始为 0。
   用 mx 保存当前所有合法左端点中的最大值，初始也为 0。由于题目中 nums[i] 都是正数，初始为 0 不会影响最终结果。

2. 2. 右端点从 k 开始遍历
   因为要求 j - i >= k，且 i 必须小于 j，所以最小的右端点 j 至少是 k。
   因此循环让 j 从 k 一直走到数组最后一个位置。

3. 3. 每次先扩大合法左端点范围
   当右端点移动到 j 时，新变得合法的左端点是 j-k。
   也就是说，之前 j 较小时，位置 j-k 还不能作为左端点；现在 j 增大了，位置 j-k 满足 j - (j-k) = k，所以它可以被选为左端点了。
   于是把 nums[j-k] 纳入考虑范围，并更新 mx：
   mx 变成原来的 mx 和 nums[j-k] 中较大的那个。
   更新后，mx 就代表从下标 0 到 j-k 这个范围内所有 nums[i] 的最大值。

4. 4. 计算以当前 j 为右端点的最佳和
   当前右端点是 nums[j]，左端点只需要选合法的最大值 mx。
   所以以 j 为右端点时，最佳有效数对和就是 mx + nums[j]。
   然后用这个和去更新全局答案 ans，使 ans 始终保存目前遇到的最大值。

5. 5. 遍历结束后返回 ans
   因为每个右端点 j 都计算了它对应的最佳左端点组合，所以最终 ans 就是所有合法数对和中的最大值。

以示例 nums = [1, 3, 5, 2, 8]，k = 2 为例：

• • 初始 ans = 0，mx = 0。

• • j = 2：把 nums[0] = 1 纳入左端点候选，mx = 1。当前右端点是 nums[2] = 5，候选和为 1 + 5 = 6，ans = 6。

• • j = 3：把 nums[1] = 3 纳入左端点候选，mx = max(1, 3) = 3。当前右端点是 nums[3] = 2，候选和为 3 + 2 = 5，ans 仍为 6。

• • j = 4：把 nums[2] = 5 纳入左端点候选，mx = max(3, 5) = 5。当前右端点是 nums[4] = 8，候选和为 5 + 8 = 13，ans 更新为 13。

• • 循环结束，返回 13。

这个方法之所以正确，是因为对于每一个右端点 j，它都只关心合法左端点范围内最大的那个值。而随着 j 不断向右移动，合法左端点范围只会扩大，不会缩小，所以可以用一个变量 mx 动态维护这个范围内的最大值，不需要每次重新扫描。

总的时间复杂度：
只对右端点 j 从 k 到 n-1 遍历一次，每次只做常数次比较和加法，因此时间复杂度是 O(n)。

总的额外空间复杂度：
只使用了 ans、mx 等常数个变量，没有额外开辟与数组规模相关的空间，因此额外空间复杂度是 O(1)。如果算输入数组本身，总空间是 O(n)，但额外空间是 O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func maxValidPairSum(nums []int, k int) (ans int) {
    mx := 0
    for j := k; j < len(nums); j++ {
        mx = max(mx, nums[j-k]) // nums[i] 的最大值
        ans = max(ans, mx+nums[j])
    }
    return
}

 func main() {
    nums := []int{1, 3, 5, 2, 8}
    k := 2
    result := maxValidPairSum(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def max_valid_pair_sum(nums, k):
    ans = 0
    mx = 0

     for j in range(k, len(nums)):
        mx = max(mx, nums[j - k])      # nums[i] 的最大值
        ans = max(ans, mx + nums[j])

     return ans

 if __name__ == "__main__":
    nums = [1, 3, 5, 2, 8]
    k = 2
    result = max_valid_pair_sum(nums, k)
    print(result)

C++完整代码如下：

  

  

  


 int maxValidPairSum(const std::vector& nums, int k) {
    int ans = 0;
    int mx = 0;
    int n = static_cast(nums.size());

     for (int j = k; j < n; ++j) {
        mx = std::max(mx, nums[j - k]);   // nums[i] 的最大值
        ans = std::max(ans, mx + nums[j]);
    }

     return ans;
}

 int main() {
    std::vector nums = {1, 3, 5, 2, 8};
    int k = 2;
    int result = maxValidPairSum(nums, k);
    std::cout << result << std::endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。