#每日一題 力扣第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;
    }
};
           

啟發：雙指針法是降低時間複雜度的一個有效的技巧，通過分析兩個變化的量之間的邏輯關系，定一動一，往往在有序隊列裡使用，被固定的指針通常都是極值。