1679. Max Number of K-Sum Pairs

Leetcode link

解题思路——排序+双指针

• TC: O(nlogn)
• SC: O(1)

题目要求我们计算在数组中任取两个不重复的数字总和为 k 的组合数，且用过的数字不能再用

那么我们可以用排序+双指针来解：

1. 先把数组由小到大排序
2. 使用两个指针分别从数组的左边跟右边开始往中间遍历
3. 如果左右指针所指元素相加小于 k ，则可以将左指针 +1来加大两数之和
4. 反之如果左右指针所指元素相加大于 k ，则可以将右指针 -1来缩小两数之和
5. 如果两数之和刚好相等，那么组合数 +1，并且把左指针 +1，右指针 -1
6. 重复步骤 2～5 直到左右指针相遇（指向同一个元素）

C++

class Solution {
 public:
  int maxOperations(vector<int>& nums, int k) {
    int res = 0, left = 0, right = nums.size() - 1;
    sort(nums.begin(), nums.end());
    while ((left < right) && (nums[left] < k)) {
      if (nums[right] + nums[left] < k) {
        left++;
      } else if (nums[right] + nums[left] > k) {
        right--;
      } else {
        left++;
        right--;
        res++;
      }
    }
    return res;
  }
};

Javascript

var maxOperations = function(nums, k) {
    let left = 0, right = nums.length-1, res = 0;
    nums.sort((a,b)=>a-b);
    while((left < right) && (nums[left] < k)) {
        if(nums[left] + nums[right] == k) {
            res++;
            right--;
            left++;
        }else if(nums[left] + nums[right] < k) {
            left++
        } else {
            right--;
        }
    }
    return res;
};

解题思路——建立映射

• TC: O(n)
• SC: O(n)

第一种方法因为用了排序使得时间复杂度比较高，那么我们可以用时间换空间的方式，也就是：

建立一个映射来保存出现过的数字的次数，然后对数组中的每个元素，在映射中找 k 与元素的差，如果在映射表中存在计数，则表示我们需要的组合出现了

C++

class Solution {
 public:
  int maxOperations(vector<int>& nums, int k) {
    int res = 0;
    unordered_map<int, int> freq;
    for (int num : nums) {
      int rest = k - num;
      if (freq[rest] > 0) {
        res++;
        freq[rest]--;
      } else {
        freq[num]++;
      }
    }
    return res;
  }
};

Javascript

var maxOperations = function(nums, k) {
    let res = 0;
    let freq = {};
    for(let num of nums) {
        let rest = k - num;
        if(freq[rest]!== undefined && freq[rest] > 0) {
            freq[rest]--;
            res++;
        } else {
            (freq[num] === undefined) && (freq[num] = 0);
            freq[num]++;
        }
    }
    return res;
};