#每日一题 力扣第28题 采购方案

先上题目：

今晚做的一道题目，虽然是简单题，但是题目有时间复杂度限制，因此需要将时间复杂度将为O（n）。

刚开始看到题目我的思路是先排序，然后双层for循环，第一层选择第一件零件，然后第二个for循环选择第二件零件再进行合法性判断。但显然会爆时间复杂度。

所以为了降低时间复杂度，我们采取双指针法来进行遍历。下面是我的代码：

class Solution {
public:int purchasePlans(vector<int>& nums, int target) {int n=0;//调用sort直接对vector进排序sort(nums.begin(),nums.end());//指针p为当前最小价格的零件，指针q为当前有可能购买到的最大价格的零件for(int p=0,q=nums.size()-1;p<q;){//超过目标价格时，说明q的价格太高，将q进行左移，选择更便宜的零件if(nums[p]+nums[q]>target){--q;//当不超过目标价格时，说明p可以和不超过q价格的零件一起被购买，此时更新可购买的方案数量，同时将最小价格零件指针p右移，选择更高价格的零件进行夹逼}else{n=(n+q-p)%1000000007;++p;}}return n;}
};

启发：双指针法是降低时间复杂度的一个有效的技巧，通过分析两个变化的量之间的逻辑关系，定一动一，往往在有序队列里使用，被固定的指针通常都是极值。