脚撕LeetCode(LCP28)Easy

示例 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^

public int purchasePlansMe(int[] nums, int target) {
    int ans = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if(nums[i] + nums[j] <= target) {
                ans++;
            }
        }
    }
    return ans;
}

public int purchasePlans(int[] nums, int target) {
        final int N = (int)1e9+7;
        long[] presum = new long[10_0001];
        for (int num : nums) {
            presum[num]++;
        }
        for (int i = 1; i < presum.length; i++) {
            presum[i] += presum[i-1];
        }
        long ans = 0;
        for (int num : nums) {
            if(num >= target)continue;
            long other = target - num;
            ans += presum[(int)other];
            if(other>=num) {
                ans--;
            }
        }
        return (int)((ans>>>1)%N);
    }