PigyChan_LeetCode 面试题 16.24. 数对和

面试题 16.24. 数对和

难度中等

设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。

示例 1:

输入: nums = [5,6,5], target = 11

输出: [[5,6]]

示例 2:

输入: nums = [5,6,5,6], target = 11

输出: [[5,6],[5,6]]

提示：

* nums.length <= 100000

思路1.0：

设置map<int val,int num> rst，意为val值出现的次数num，将nums中的所有信息转移到rst中。通过遍历rst，同时减去当前遍历值和其配对值的num，并把这对数加入到rst中。

代码1.0：

class Solution {
public:
    vector<vector<int>> pairSums(vector<int>& nums, int target) {
        if (nums.empty()) return {};
        map<int, int>rst;
        vector<vector<int>> ans;


        for (const auto& i : nums) {
            rst[i]++;
        }


        for (auto& i : rst) {
            if (i.second == 0) continue;


            if (target - i.first == i.first) {
                int time = i.second / 2;
                for (int k = 0; k < time; ++k) {
                    ans.push_back(vector<int>({ i.first,i.first }));
                }
                i.second = 0;
            }
            else {
                auto mery = rst.find(target - i.first);


                int time = min(i.second, mery->second);
                for (int k = 0; k < time; ++k) {
                    ans.push_back(vector<int>({ i.first,mery->first }));
                }
                i.second = 0;
                mery->second = 0;
            }


        }


        return ans;
    }
};