-
Notifications
You must be signed in to change notification settings - Fork 0
/
maxNumberOfK-SumPairs.go
59 lines (54 loc) · 1.1 KB
/
maxNumberOfK-SumPairs.go
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package _021_05
import "sort"
// Max Number of K-Sum Pairs
// leetcode: https://leetcode-cn.com/problems/max-number-of-k-sum-pairs/
// 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.
func MaxNumberOfKSumPairs(nums []int, k int) int {
count := 0
sort.Ints(nums)
left, right := 0, len(nums) - 1
for left < right {
sum := nums[left] + nums[right]
if sum > k {
right--
}else if sum < k {
left++
}else {
count++
left++
right--
}
}
return count
}
// hash
func MaxNumberOfKSumPairs2(nums []int, k int) int {
counts := make(map[int]int)
for _, num := range nums {
counts[num]++
}
ans := 0
for num, count := range counts {
if count == 0 {
continue
}
if num * 2 == k {
ans += count / 2
counts[num] = 0
}
if c, ok := counts[k-num]; ok {
ans += min(c, count)
counts[num] = 0
counts[k-num] = 0
}
}
return ans
}
func min(a, b int) int {
if a > b {
return b
}
return a
}