LeetCode 75 第十三题(1679)K和数对的最大数目-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 75 第十三题(1679)K和数对的最大数目。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目:

LeetCode 75 第十三题(1679)K和数对的最大数目,LeetCode75题解,leetcode,算法,数据结构,c++

示例:

LeetCode 75 第十三题(1679)K和数对的最大数目,LeetCode75题解,leetcode,算法,数据结构,c++

分析:

给一个数组，两个和为K的数为一组，问能凑成几组。

既然一组是两个数，那么我们可以使用双指针分别指向数组首尾，然后再判断能否凑成和为K的组.

在使用双指针寻找之前,我们应当先将数组排序(升序降序都无所谓),我们这里采用C++sort的默认升序.

然后左右指针分别指向数组首尾,将指针所指元素加起来,若是大于K,则需要减小指针所指元素总和,由于是排序后的数组,因此需要左移右指针,然后再进行判断.

碰到和为K的组后,将res++,并且同时移动两个指针,因为题目是说找到数对后将其移出数组,但是我们没有移出,所以只要指针不再指向它们,也就约等于是移出了.

左右指针向中间靠拢,知道双指针重叠则寻找完毕.

LeetCode 75 第十三题(1679)K和数对的最大数目,LeetCode75题解,leetcode,算法,数据结构,c++

代码+运行结果:

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

LeetCode 75 第十三题(1679)K和数对的最大数目,LeetCode75题解,leetcode,算法,数据结构,c++ 文章来源地址https://www.toymoban.com/news/detail-617101.html