LeetCode 솔루션 분류
[5/4] 1679. Max Number of K-Sum Pairs
본문
[LeetCode 시즌 3] 2022년 5월 4일 문제입니다.
https://leetcode.com/problems/max-number-of-k-sum-pairs/
[Medium] 1679. 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.
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 <= 105
1 <= nums[i] <= 109
1 <= k <= 109
관련자료
-
링크
댓글 3
나무토끼님의 댓글
- 익명
- 작성일
Runtime: 1132 ms, faster than 15.18% of Python3 online submissions for Max Number of K-Sum Pairs.
Memory Usage: 25.9 MB, less than 97.77% of Python3 online submissions for Max Number of K-Sum Pairs.
Memory Usage: 25.9 MB, less than 97.77% of Python3 online submissions for Max Number of K-Sum Pairs.
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
ans = 0
hash_table = defaultdict(int)
while nums:
temp = nums.pop()
if hash_table[temp] > 0:
ans += 1
hash_table[temp] -= 1
else:
hash_table[k - temp] += 1
return ans
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 213 ms, faster than 40.70% of C++ online submissions for Max Number of K-Sum Pairs.
Memory Usage: 72.8 MB, less than 26.77% of C++ online submissions for Max Number of K-Sum Pairs.
Runtime: 213 ms, faster than 40.70% of C++ online submissions for Max Number of K-Sum Pairs.
Memory Usage: 72.8 MB, less than 26.77% of C++ online submissions for Max Number of K-Sum Pairs.
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
unordered_map<int, int> counter;
int n = nums.size();
int res = 0;
for (int i = 0; i < n; ++i) {
int target = k - nums[i];
if (counter[target] > 0) {
counter[target]--;
res++;
}
else {
counter[nums[i]]++;
}
}
return res;
}
};
austin님의 댓글
- 익명
- 작성일
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
unordered_map<int, int> m;
int ret = 0;
for(auto n : nums) {
if (m[k-n] > 0) {
++ret;
--m[k-n];
} else ++m[n];
}
return ret;
}
};