엔지니어 게시판
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.
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.
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;
    }
};
전체 94 / 4 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 914 명
  • 오늘 방문자 5,536 명
  • 어제 방문자 6,932 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,481 명
알림 0