1679. Max Number of K-Sum Pairs.md

1679. Max Number of K-Sum Pairs

---

the second one in Weekly Contest 218.

leetcode Daily Challenge on January 18th, 2021.

---

Difficulty : Medium

Related Topics : HashTable

---

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 <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9

---

Solution

• mine
  • Java
    • Runtime: 31 ms, faster than 64.29%, Memory Usage: 52.8 MB, less than 66.07% of Java online submissions

      // O(N)time
      // O(N)space
      public int maxOperations(int[] nums, int k) {
          Map<Integer,Integer> map = new HashMap<>();
          int res = 0;
          for(int num : nums){
              int t = k - num;
              int v = map.getOrDefault(t, 0);
              if(v > 0){
                  map.put(t, v - 1);
                  res++;
              }else{
                  map.put(num, map.getOrDefault(num, 0) + 1);
              }
          }
          return res;
      }
      

---

• the most votes

• Runtime: 16 ms, faster than 98.44%, Memory Usage: 48.2 MB, less than 93.24% of Java online submissions

  // O(N*logN)time
  // O(1) or O(N)space depends on sort
  public int maxOperations(int[] nums, int k) {
      Arrays.sort(nums);
      int count = 0;
  
      int i = 0;
      int j = nums.length - 1;
  
      while(i<j) {
          if(nums[i] + nums[j] > k) {
              j--;
          } else if(nums[i] + nums[j] < k) {
              i++;
          } else {
              count++;
              i++;
              j--;
          }
      }
      return count;
  }
  

---