当前位置:网站首页>Leetcode 5618. Maximum number of K sum pairs (hash)

Leetcode 5618. Maximum number of K sum pairs (hash)

2020-12-06 15:49:50 Michael Amin

1. subject

Give you an array of integers nums And an integer k .

In every step of the operation , You need to pick from the array And for k Two integers of , And move them out of the array .

Returns what you can execute on an array Maximum operands .

 Example  1:
 Input :nums = [1,2,3,4], k = 5
 Output :2
 explain : At the beginning of the  nums = [1,2,3,4]-  Removed from the  1  and  4 , after  nums = [2,3]
-  Removed from the  2  and  3 , after  nums = []
 No more and for  5  The number of , So at most  2  operations .

 Example  2:
 Input :nums = [3,1,3,4,3], k = 6
 Output :1
 explain : At the beginning of the  nums = [3,1,3,4,3]-  Remove the first two  3 , after nums = [1,4,3]
 No more and for  6  The number of , So at most  1  operations .
 
 Tips :
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9

source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/max-number-of-k-sum-pairs
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Problem solving

class Solution {
    
public:
    int maxOperations(vector<int>& nums, int k) {
    
    	unordered_map<int, int> m;
    	for(auto n : nums)
    		m[n]++;// Hash count 
    	int sum = 0, num, count, target, add;
    	for(auto& num_count : m)
    	{
    
    		num = num_count.first;// Numbers 
    		count = num_count.second;// Number 
    		if(count == 0)
    			continue;
    		target = k-num;// Another number 
            if(m.find(target) != m.end())// Another number exists 
            {
    
                if(target != num)// It's not equal 
    	            add = min(count, m[target]);
                else if(target == num)// equal 
                    add = count/2;
                sum += add;// Operands 
                num_count.second -= add;// Original count   Subtract the manipulated 
                m[target] -= add;
            }
    	}
    	return sum;
    }
};

352 ms 66.5 MB C++


my CSDN Blog address https://michael.blog.csdn.net/

Long click or sweep code pay attention to my official account (Michael amin ), Come on together 、 Learn together !
Michael amin

版权声明
本文为[Michael Amin]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201206154645133w.html