采购方案

难度: Easy

小力将 N 个零件的报价存于数组 `nums`。小力预算为 `target`，假定小力仅购买两个零件，要求购买零件的花费不超过预算，请问他有多少种采购方案。注意：答案需要以 `1e9 + 7 (1000000007)` 为底取模，如：计算初始结果为：`1000000008`，请返回 `1` **示例 1：** >输入：`nums = [2,5,3,5], target = 6` > >输出：`1` > >解释：预算内仅能购买 nums[0] 与 nums[2]。 **示例 2：** >输入：`nums = [2,2,1,9], target = 10` > >输出：`4` > >解释：符合预算的采购方案如下： >nums[0] + nums[1] = 4 >nums[0] + nums[2] = 3 >nums[1] + nums[2] = 3 >nums[2] + nums[3] = 10 **提示：** - `2 <= nums.length <= 10^5` - `1 <= nums[i], target <= 10^5`

Submission

运行时间: 136 ms

内存: 26.7 MB

class Solution:
    def purchasePlans(self, nums: List[int], target: int) -> int:
        ans=0
        nums.sort()
        l,r=0,len(nums)-1
        while l<r:
            if nums[r]+nums[l]<=target:
                ans+=r-l
                l+=1
            else:
                r-=1
        return ans%1000000007

Explain

此题解使用了双指针技巧。首先，将数组排序，然后使用两个指针，一个指向数组的开始（左指针），另一个指向数组的末尾（右指针）。左指针代表的是较小的数，右指针代表的是较大的数。不断检查两个指针所指的数之和是否小于等于目标值 target。如果是，则所有介于左指针和右指针之间的组合都满足条件（因为数组是排序的，所以右指针左边的任何一个数字加上左指针的数字都会小于等于target），于是将这些组合计入答案中。然后移动左指针向右寻找新的组合。如果两数之和大于 target，则移动右指针向左以减小数值之和。这个过程持续到左指针不再小于右指针。

时间复杂度: O(n log n)

空间复杂度: O(log n)

# 定义Solution类
class Solution:
    def purchasePlans(self, nums: List[int], target: int) -> int:
        ans = 0  # 初始化答案计数器
        nums.sort()  # 对数组进行排序
        l, r = 0, len(nums) - 1  # 初始化左右指针
        while l < r:  # 当左指针小于右指针时继续循环
            if nums[r] + nums[l] <= target:  # 如果当前两指针指向的值的和小于等于目标值
                ans += r - l  # 将右指针与左指针之间的差加到答案中
                l += 1  # 移动左指针向右
            else:
                r -= 1  # 否则移动右指针向左
        return ans % 1000000007  # 返回结果，结果需要取模

Explore

在这个问题中，对数组进行排序是必要的步骤，因为排序后数组的元素顺序保证了从小到大排列。这样在使用双指针策略时，可以有效地控制和调整指针以找到所有满足条件的组合。具体来说，当左指针指向的元素比较小，右指针指向的元素比较大时，如果这两个元素的和小于等于目标值，则左指针左侧的所有元素与右指针指向的元素的和也必然小于等于目标值。这种性质只有在数组有序的情况下才成立，因此排序是实现双指针策略的前提。

在双指针策略中，当两个指针指向的元素之和小于等于目标值时，由于数组是排序的，左指针（l）指向的是较小的元素，右指针（r）指向的是较大的元素。此时，位于左指针和右指针之间的任何一个元素与左指针指向的元素相加也一定小于等于目标值。因此，右指针到左指针之间的所有元素（包括右指针但不包括左指针），都可以与左指针组合构成有效的购买方案。这些组合的数量正是右指针与左指针的位置差（r - l），因此可以直接将这个值加到答案总数上。

如果数组中的所有元素都非常接近目标值 `target`，在使用双指针方法时可能会导致右指针频繁地向左移动以调整和值以适应目标条件。在这种情况下，即使每次调整后都可能发现较少的有效组合，整体算法效率依然保持较高，因为每一步右指针的移动都是有目的的—即寻找不超过目标值的元素组合。由于双指针策略本质上是线性扫描数组，因此算法的时间复杂度为O(n)，即使在这种极端情况下，算法的效率仍然较高。