1679. K 和数对的最大数目 Medium

给你一个整数数组 nums 和一个整数 k 。

每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。

返回你可以对数组执行的最大操作数。

示例 1：
输入：nums = [1,2,3,4], k = 5
输出：2
解释：开始时 nums = [1,2,3,4]：
移出 1 和 4 ，之后 nums = [2,3]
移出 2 和 3 ，之后 nums = []
不再有和为 5 的数对，因此最多执行 2 次操作。

示例 2：
输入：nums = [3,1,3,4,3], k = 6
输出：1
解释：开始时 nums = [3,1,3,4,3]：
移出前两个 3 ，之后nums = [1,4,3]
不再有和为 6 的数对，因此最多执行 1 次操作。

解题思路

输入： 一个整数数组 nums 和一个整数 k

输出： 每次操作可以选出两个和为 k 的整数，返回最多可以操作几次

本题属于 可变长度滑动窗口类型 类型。

我们首先将数组排序后再利用双指针构建滑动窗口

• 当左右窗口的值 < k，则移动左窗口
• 当左右窗口的值 > k，则移动右窗口
• 当左右窗口的值 = k，则记录一次操作数并且移动左右两个窗口

最后返回操作数

代码实现

python

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        # 将数组 `nums` 排序
        nums.sort()

        # 初始化两个指针，`l` 指向数组的开始，`r` 指向数组的末尾
        l, r = 0, len(nums) - 1

        # 用于记录满足条件的配对数量
        ans = 0

        # 当左指针小于右指针时继续循环
        while l < r:
            # 如果当前两个数的和大于目标值 `k`
            if nums[l] + nums[r] > k:
                # 将右指针向左移动以尝试减小和
                r -= 1
            # 如果当前两个数的和小于目标值 `k`
            elif nums[l] + nums[r] < k:
                # 将左指针向右移动以尝试增大和
                l += 1
            else:
                # 如果当前两个数的和等于目标值 `k`
                ans += 1  # 记录一个有效的配对
                l += 1    # 移动左指针到下一个位置
                r -= 1    # 移动右指针到下一个位置
        
        # 返回找到的有效配对数量
        return ans

javascript

var maxOperations = function(nums, k) {
    nums.sort((a, b) => a - b);

    let l = 0;
    let r = nums.length - 1;
    let ans = 0;

    while (l < r) {
        if (nums[l] + nums[r] < k) {
            l++;
        } else if (nums[l] + nums[r] > k) {
            r--;
        } else {
            ans++;
            l++;
            r--;
        }
    }

    return ans;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

1679 国际版

1679 中文版