What is the approach to solving Max Number of K-Sum Pairs?

You can solve this problem using a hash table to store element counts or by applying the two-pointer technique after sorting the array.

What is the time complexity of the hash table approach?

The hash table approach runs in O(n) time, where n is the length of the array.

How do I avoid reusing elements in pairs?

By ensuring that once a pair is formed, both elements are removed or reduced in the hash table or array.

What if the array contains duplicates in Max Number of K-Sum Pairs?

Duplicates can still form valid pairs as long as they satisfy the sum condition, and each element can only be used once.

Can I use brute force to solve Max Number of K-Sum Pairs?

Brute force is not efficient and should be avoided because it leads to a time complexity of O(n^2). A hash table or two-pointer approach is much more efficient.

#1679

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

K 和数对的最大数目

给你一个整数数组 nums 和一个整数 k 。每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。返回你可以对数组执行的最大操作数。示例 1：输入： nums = [1,2,3,4], k = 5 输出： 2 解释：开始时 nums = [1,2,3,4]： - 移出 …

数组哈希表双指针排序

题目描述

给你一个整数数组 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⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹

lightbulb

解题思路

方法一：排序

我们对 $nums$ 进行排序。然后 $l$ , $r$ 分别指向 $nums$ 首尾元素，判断两整数之和 $s$ 与 $k$ 的大小关系。

若 $s = k$ ，说明找到了两个整数，满足和为 $k$ ，答案加一，然后 $l$ , $r$ 向中间移动；
若 $s \gt k$ ，则 $r$ 指针向左移动；
若 $s \lt k$ ，则 $l$ 指针向右移动；
继续循环判断，直至 $l \geq r$ 。

循环结束，返回答案。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        nums.sort()
        l, r, ans = 0, len(nums) - 1, 0
        while l < r:
            s = nums[l] + nums[r]
            if s == k:
                ans += 1
                l, r = l + 1, r - 1
            elif s > k:
                r -= 1
            else:
                l += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates knowledge of hash tables for efficiently pairing elements.
question_mark
The candidate employs greedy algorithms or two-pointer techniques to find pairs in linear time.
question_mark
The candidate shows understanding of time-space trade-offs when deciding between hash table and sorting approaches.

warning

常见陷阱

外企场景

error
Failing to check if elements are still available in the hash table before forming pairs can lead to overcounting.
error
Not handling edge cases like no pairs existing or repeated elements in the array.
error
Using inefficient approaches like brute force pair finding, which would result in O(n^2) time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to find k-sum pairs instead of pairs, expanding the problem to larger sums.
arrow_right_alt
Change the problem so that you need to return the sum of the elements in the valid pairs.
arrow_right_alt
Add constraints where the array contains duplicates, and elements can only be used once in all pairs.

help

常见问题

外企场景

继续练习

#1782 统计点对的数目 #1346 检查整数及其两倍数是否存在 #1048 最长字符串链