[数据结构与算法]leetcode 1679. Max Number of K-Sum Pairs（和为k的数字对）

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.

在一个数组中找到所有的一对数字，使它们的和为k。

思路：
变相版的2 sum问题。

会想到把访问过的数字保存在HashSet里面，然后找k-另一数字，
但是，本题的数组是可以有重复数字的，所以不能用HashSet，
但是可以用HashMap，记录每个数字出现的次数，用过一次次数减1。
这种方法时间效率不咋地。

    public int maxOperations(int[] nums, int k) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        
        map.put(nums[0], 1);
        
        for(int i = 1; i< n; i++) {
            int num = k - nums[i];
            
            if(map.containsKey(num)) {
                map.put(num, map.get(num) - 1);
                if(map.get(num) == 0) map.remove(num);
                res ++;
            } else {
                if(!map.containsKey(nums[i])) map.put(nums[i], 1);
                else map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        return res;
    }

两个数字之和还可以用双指针，
和 < k 时把左指针右移，和 > k 就把右指针左移。
但是记得要先排序。

    public int maxOperations(int[] nums, int k) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        int res = 0;
        
        Arrays.sort(nums);
        
        while(left < right) {
            int sum = nums[left] + nums[right];
            if(sum == k) {
                res ++;
                left ++;
                right --;
            } else if (sum < k) {
                left ++;
            } else {
                right --;
            }
        }
        return res;
    }

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖