0%

LeetCode 1679. Max Number of K-Sum Pairs

Posted on In

题目

原题在此
You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:

  • Remove numbers 1 and 4, then nums = [2,3]
  • Remove numbers 2 and 3, then nums = []
    There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:

  • Remove the first two 3’s, then nums = [1,4,3]
    There are no more pairs that sum up to 6, hence a total of 1 operation.

Constraints:

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

解析

思路一

这题和LeetCode第一题2Sum很像, 做过就会想到用空间换时间, 建立map来缩短查询时间.

  1. 建立一个map<num, count>, 遍历数组, 记录每个数字出现的次数.
  2. 遍历map, 如果有 map[k - key]存在, 则说明有可以相加等于k的两个数字存在, 此时有两种情况:
    1. key == k - key, 即两个相同数字相加等于k, 此时结果应该加上 map[key] / 2.
    2. key != k - key, 即两个不同数字相加等于k, 此时结果应该加上 min(map[key], map[k- key]), 即最多可以有两个count中较小值个数的pair. 且因为key != k - key, 之后还会遍历到一次相同的pair, 这里需要减去min值, 以便在第二次处理相同pair时 min()会返回0.

思路二

在理解了用map记录每个num的出现次数和查询 key 与 k - key的count关系后, 可以将算法改进. 将记录与查询过程放入一个循环, 一次搞定.

  1. 建立一个map<num, count>, 遍历nums数组
    1. 若 num >= k, 即当前num不可能组成pair, 跳过本次循环.
    2. 若 map[k - num]有值且大于0, 则能组成pair, res++; map[k - num]--. 否则map[num]++.

代码

方法一(golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func maxOperations(nums []int, k int) int {
    m := make(map[int]int)
    res := 0
    for _, val := range nums {
        m[val]++
    }
    
    for key, val := range m {
        if v, ok := m[k - key]; ok {
            if(k - key == key) {
                res += val / 2;
            } else {
                less := min(val, v)
                res += less
                m[key] -= less
                m[k - key] -= less
            }
        }
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

方法二(golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func maxOperations(nums []int, k int) int {
    m := make(map[int]int)
    res := 0
    for _, num := range nums {
        if num >= k {
            continue
        }
        diff := k - num
        count := m[diff]
        if count > 0 {
            res++
            m[diff]--
        } else {
            m[num]++
        }
    }
    return res
}