寒假刷题Day17

一、2824. 统计和小于目标的下标对数目

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

  // 如果 nums[left] + nums[right] < target，那么 nums[left] 与 nums[left+1..right] 都满足条件

二、LCP 28. 采购方案

class Solution {
public:
    int purchasePlans(vector<int>& nums, int target) {
        long long res = 0;
        long long mod = 1000000007;
        sort(nums.begin(),nums.end());
        int i=0,j = nums.size()-1;
        for(i=0;i<j;i++)
        {
            while(j>i&&nums[i]+nums[j]>target)
            {
                j--;
            }
            res += j-i;
        }
        return res%mod;
    }
};

题目给我整懵了，还是看题解才明白意思，来自ai的解释：

小力的问题有一个特别的小要求哦～听好啦：

🌟 魔法数字游戏规则 🌟
如果答案是一个超级超级大的数字（比如像天上的星星那么多），我们要用一个魔法数字（1000000007）来帮忙。
怎么玩呢？
1️⃣ 先算出答案（比如 1000000008）。
2️⃣ 减去魔法数字（1000000007），剩下的就是小答案（1000000008 - 1000000007 = 1）。
3️⃣ 最后告诉小力的是这个小答案（1）哦！

就像数到 10 要重新从 1 开始一样，数到魔法数字也要重新开始！✨

三、15. 三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 剪枝
        if(nums.size() < 3)return{};


        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;

        for(int i = 0; i < nums.size(); ++i){
            // 检测重复的 nums[i]
            if(i > 0 && nums[i] == nums[i-1]) continue;

            int left = i + 1;
            int right = nums.size() - 1;

            // 比较三数之和           
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];

                // 去重
                while(left <right && nums[left] == nums[left + 1]) left++;
                while(left < right && nums[right] == nums[right - 1]) right--;

                // 去重后两数之和
                if(sum > 0) right--;

                // 等同于判断 nums[l] + nums[r] < -nums[i]
                else if(sum < 0) left++;

                // nums[l] + nums[r] == nums[i], 三元组符合，添加入结果
                else {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    left++; 
                    right--;
                }
            }
        }
        return ans;
    }
};