采购方案

LCP 28. 采购方案

难度 简单

小力将 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

双指针解法

class Solution {
    public int purchasePlans(int[] nums, int target) {
        int mod = 1_000_000_007;
        int ans = 0;
        // 首先对整体进行排序
        Arrays.sort(nums);
        // 双指针，left 从前往后找，right 从后往前
        int left = 0, right = nums.length - 1;
        while (left < right) {
            // 如果当前左右之和大于了目标值，说明偏大了，就把右指针往左移动
            if (nums[left] + nums[right] > target) right--;
            else {
                // 否则的话，说明找到了合适的，需要把两者中间的元素个数都累加起来
                ans += right - left;
                // 然后再向右移动左指针
                left++;
            }
            ans %= mod;
        }
        return ans % mod;
    }
}

作者：hxz1998
链接：https://leetcode-cn.com/problems/4xy4Wx/solution/java-shuang-zhi-zhen-fa-zhu-xing-zhu-shi-pja9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二分查找解法

class Solution {
    public int purchasePlans(int[] nums, int target) {
        Arrays.sort(nums);
        int result = 0;
        for(int i = 0;i<nums.length - 1;i++){
            int low = i;
            int high = nums.length - 1;


            while(low<=high){
                int mid = (high + low) /2;
                if(mid == i){
                    low++;
                    continue;
                }
                if(nums[i] + nums[mid] < target){
                    low = mid + 1;
                }else if (nums[i] + nums[mid] > target){
                    high = mid - 1;
                }else {
                    low = mid + 1;
                }

            }

            result += (high - i);
            result %= 1000000007;
        }
        return result%1000000007;
    }
}

作者：lanwu
链接：https://leetcode-cn.com/problems/4xy4Wx/solution/java-pai-xu-jia-er-fen-by-lanwu-xv3u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

两数之和解法

class Solution {
    public int purchasePlans(int[] nums, int target) {

        int mod = (int) 1e9 + 7;
        int n = nums.length;
        Arrays.sort(nums);
        Set<Integer> set = new HashSet<>();
        int[][] big = new int[100001][2];
        for (int i = 0; i < n; i++) {
            big[nums[i]][0] = i + 1;
            big[nums[i]][1]++;
            set.add(nums[i]);
        }

        for (int i = 1; i < 100000; i++) {
            if (big[i][0] == 0) {
                big[i][0] = big[i - 1][0];
            }
        }

        long res = 0;
        for (int val : set) {
            int t = target - val;
            if (val <= t) {
                int v = big[t][0];
                res = (res + ((long)big[val][1] * (big[val][1] - 1) / 2)) % mod;
                res = (res + ((long)big[val][1] * (v - big[val][0]))) % mod;
            }
        }
        return (int) (res % mod);
    }
}

赏

谢谢你请我吃糖果

微信