LeetCode 솔루션

[5/4] 1679. Max Number of K-Sum Pairs

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.03 22:08

4,643 조회
3 댓글
0 추천
0 비추천
목록 게시글 쓰기

[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

#LeetCode, #Amazon, #Array, #Hash Table, #Two Pointers, #Sorting

링크

https://leetcode.com/problems/max-number-of-k-sum-pairs/ 1139 회 연결

익명
작성일 2022.05.04 11:44

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.

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

익명
작성일 2022.05.04 17:18

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.

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;
    }
};

익명
작성일 2022.05.05 01:24

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;
    }
};