成都網(wǎng)站建設028net,徐州網(wǎng)站開發(fā)培訓,wordpress在什么系統(tǒng)下搭建,黃頁軟件app大全小力將 N 個零件的報價存于數(shù)組 nums。小力預算為 target#xff0c;假定小力僅購買兩個零件#xff0c;要求購買零件的花費不超過預算#xff0c;請問他有多少種采購方案。注意#xff1a;答案需要以 1e9 7 (1000000007) 為底取模#xff0c;如#xff1a;計算初始結(jié)果…小力將 N 個零件的報價存于數(shù)組nums。小力預算為target假定小力僅購買兩個零件要求購買零件的花費不超過預算請問他有多少種采購方案。注意答案需要以1e9 7 (1000000007)為底取模如計算初始結(jié)果為1000000008請返回1思路因為只需要買兩個零件考慮到只需要計算兩個數(shù)值的和是否在預算以內(nèi)即可故而采用雙指針的辦法依次判斷之和是否滿足條件即可。最后結(jié)果對1000000007取余即可因為可能零件和預算變大之后方法也會變多。主要難理解的可能是其中判斷依據(jù)排序后為什么是right-left是一個數(shù)學問題他如果最小的和最大的和滿足題意等價于一個搭配問題兩個兩個取能取幾次是個排列問題他的次數(shù)為最右邊的序數(shù)減去最左邊的序數(shù)就是次數(shù)。class Solution: def purchasePlans(self,nums:List[int],target:int)-int: left,right0,len(nums)-1 count0 nums.sort() while leftright: if nums[left]nums[right]target: countright-left left1 else: right-1 return count%1000000007難點分析排序保證了 “單調(diào)性”左指針固定時右指針往左的所有數(shù)都更小因此和左指針的和也更小雙指針的 “貪心”找到最大的合法右指針就能覆蓋所有更小的右指針的合法情況計數(shù)的 “數(shù)學本質(zhì)”left1到right的元素個數(shù) 終止索引 - 起始索引 right - left起始索引是 left1終止索引是 right → 個數(shù) right - (left1) 1 right - left。