11. Count Number Pairs

Origin: Count Number Pairs

Given a sorted array of positive integers and a target value, count the number of pairs (i, j) where i < j and array[i] + array[j] <= target.

Example

Input: prices = [1, 2, 3, 4, 5] budget = 7

Output: 8

Explanation: We need pairs (i, j) with i < j and prices[i] + prices[j] ≤ 7. List all pairs:

• (1, 2) = 3 ≤ 7
• (1, 3) = 4 ≤ 7
• (1, 4) = 5 ≤ 7
• (1, 5) = 6 ≤ 7
• (2, 3) = 5 ≤ 7
• (2, 4) = 6 ≤ 7
• (2, 5) = 7 ≤ 7
• (3, 4) = 7 ≤ 7

Pairs like (3,5)=8, (4,5)=9 exceed the budget. Total valid pairs = 8.

Input Format

The first line contains two space-separated integers n and budget, where:

• 0 ≤ n ≤ 1000
• 1 ≤ budget ≤ 10

The second line contains n space-separated integers prices[0], prices[1], …, prices[n-1], where:

• 1 ≤ prices[i] ≤ 10^9 for all 0 ≤ i < n
• prices is sorted in non-decreasing order

Constraints

• 0 ≤ prices.length ≤ 1000
• 1 ≤ prices[i] ≤ 10^9 for all 0 ≤ i < prices.length
• prices is sorted in non-decreasing order
• 1 ≤ budget ≤ 10
• All inputs are integers

Output Format

Output a single integer representing the total count of unique index pairs (i, j) with 0 ≤ i < j < n such that prices[i] + prices[j] ≤ budget. If n < 2, output 0.

Sample Input 0

0 100

Sample Output 0

0

Sample Input 1

1 5
5

Sample Output 1

0

---

函数契约

// 输入：prices（有序正整数数组），budget（预算上限）
// 输出：满足 i < j 且 prices[i] + prices[j] <= budget 的对数（整数）
// 边界：n < 2 → 0；所有对都超预算 → 0；所有对都满足 → n*(n-1)/2

边界表

场景	返回什么
n < 2（空数组或单元素）	0
最小两数之和 > budget	0
最大两数之和 <= budget	n*(n-1)/2
正常场景	计数

Resolution

我的解法

解法一：暴力枚举

function countAffordablePairs(prices: number[], budget: number): number {
    let count = 0;
    for (let i = 0; i < prices.length - 1; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            if (prices[i] + prices[j] <= budget) {
                count++
            }
        }
    }
    return count;
}

两层 for 循环遍历所有对，简单直接。

解法二：双指针（最优解）

function countAffordablePairs(prices: number[], budget: number): number {
    let count = 0;
    let i = 0;
    let j = prices.length - 1;
    while (i < j) {
        const total = prices[i] + prices[j]
        if (total <= budget) {
            count += j - i;
            i++;
        }
        else {
            j--;
        }
    }
    return count;
}

解题思路

这道题的突破口是”数组有序”。

双指针从头尾出发：

• 如果 prices[i] + prices[j] <= budget，因为数组有序，i 到 j-1 之间的所有元素都和 j 配对满足条件，数量是 j - i，然后 i 右移
• 否则 j 左移，缩小和值

关键一步是 count += j - i，利用有序性一次性算出满足条件的对数，避免了内层循环。这和”空间换时间”不同，靠的是数据结构本身的性质（有序性）优化时间。

复杂度

暴力枚举：

• 时间：O(n²)
• 空间：O(1)

双指针：

• 时间：O(n)，一次遍历
• 空间：O(1)，两个指针

参考来源

• 相关文章：算法解题思路：边界条件与返回值
• 相关文章：算法解题流程：从读题到提交的七步