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。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

解题思路

这道题要求找出数组中能组成和为 k 的数对的最大数量。有三种主要解法：

解法分析

1. 哈希表计数法（推荐）

  • 使用哈希表统计每个数字的出现次数
  • 对于每个数字 x，查看是否存在 k-x
  • 如果 x = k-x（即 x = k/2），则配对数为 count[x]/2
  • 否则配对数为 min(count[x], count[k-x])
  • 时间复杂度 O(n)，空间复杂度 O(n)

2. 双指针法

  • 先对数组排序，然后使用左右双指针
  • 如果 nums[left] + nums[right] = k，则找到一对，两指针都移动
  • 如果和小于 k，左指针右移；如果和大于 k，右指针左移
  • 时间复杂度 O(n log n)，空间复杂度 O(1)

3. 贪心匹配法

  • 遍历数组，对每个元素尝试找到配对
  • 使用哈希表记录已访问但未配对的元素
  • 时间复杂度 O(n)，空间复杂度 O(n)

哈希表计数法最为直观高效，是最推荐的解法。

代码实现

class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        int operations = 0;
        for (auto& [num, cnt] : count) {
            int complement = k - num;
            if (num == complement) {
                operations += cnt / 2;
            } else if (count.count(complement) && num < complement) {
                operations += min(cnt, count[complement]);
            }
        }
        
        return operations;
    }
};

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        from collections import Counter
        
        count = Counter(nums)
        operations = 0
        
        for num, cnt in count.items():
            complement = k - num
            if num == complement:
                operations += cnt // 2
            elif complement in count and num < complement:
                operations += min(cnt, count[complement])
        
        return operations

public class Solution {
    public int MaxOperations(int[] nums, int k) {
        var count = new Dictionary<int, int>();
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        int operations = 0;
        foreach (var pair in count) {
            int num = pair.Key;
            int cnt = pair.Value;
            int complement = k - num;
            
            if (num == complement) {
                operations += cnt / 2;
            } else if (count.ContainsKey(complement) && num < complement) {
                operations += Math.Min(cnt, count[complement]);
            }
        }
        
        return operations;
    }
}

var maxOperations = function(nums, k) {
    const map = new Map();
    let operations = 0;
    
    for (let num of nums) {
        const complement = k - num;
        if (map.get(complement) > 0) {
            operations++;
            map.set(complement, map.get(complement) - 1);
        } else {
            map.set(num, (map.get(num) || 0) + 1);
        }
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
哈希表计数法O(n)O(n)
双指针法O(n log n)O(1)

其中 n 为数组长度。推荐使用哈希表计数法，在时间复杂度上最优。

相关题目