统计和小于目标的下标对数目 图解题解

数出多少对下标，和严格小于 target

给一个下标从 0 开始的数组 nums 和整数 target，数出多少对下标 (i, j) 满足 i 在 j 前面、且 nums[i] 加 nums[j] 严格小于 target。是严格小于，取等不算。题面 nums=[-1,1,2,3,1]、target=2 时答案 3。

两重循环把每对都试一遍，代价在哪

双重循环能数：外层挑 i、内层挑 j，逐对把两数之和和 target 比，严格小于就计数。n 个数约 n 方 ÷ 2 对，要比这么多次，时间 O(n²)。这题 n 不超过 50 硬枚举也能过，但一对对试没占便宜，排好序就能把「逐对试」改成「一整批一次数完」。

排序打乱了原下标，为什么不影响对数

题目只问「有多少对」，不追问是原数组哪两个位置——(i, j) 和 (j, i) 是同一对，跟原位置无关。把 nums 排好序，值不变，能凑成的对一个不多不少，答案完全一样。排序换来有序：任取一个数当右端，它左边的数都不比它大，能配成小于 target 的对的，都在左段前一截。

固定右端 nums[j]，左边有几个能配上

从左到右让每个 nums[j] 当右端。要和它配对的左伙伴 nums[i]（i 在 j 左边）得满足 nums[i] 小于 target 减 nums[j]。左段 nums[0..j-1] 本身升序，比这阈值小的数都挤在最前一截，数有几个不必逐个看，二分（在有序段里对半缩着定位）找出这截右边界即可。

代码写成 bisect_left(nums, target − nums[j], hi=j)：在 0 到 j（不含 j，即 hi=j 的作用）里找第一个不小于阈值的位置，这下标值恰好是它左边严格小于阈值的个数，即能配 nums[j] 的左伙伴数。累加各右端即得答案。

排完序的 [-1,1,1,2,3]，各右端配到几个

先排序，[-1,1,2,3,1] 变成 [-1,1,1,2,3]，逐个取右端，阈值是 target 减右端值。-1 当右端左边空着，配 0；第一个 1 当右端阈值 1，左边只有 -1 小于 1，配 1；第二个 1 阈值仍 1，也只有 -1 合格，配 1；2 阈值 0，仍只有 -1 小于 0，配 1；3 阈值 -1，左边没有更小的，配 0。

各右端配到的数加起来 0+1+1+1+0，正是题面给的 3。三对左伙伴都是 -1，加 1、1、2 得 0、0、1，全小于 2。

严格小于这道坎，bisect 该用左不用右

阈值那步最容易走偏。要的是 nums[i] 严格小于 target − nums[j]，对应 bisect_left（第一个不小于阈值的位置，返回值正是严格小于阈值的个数）；换成 bisect_right，等于阈值的数也算进，即和恰好等于 target 的对，取等本该排除。hi 也要钉在 j 上：hi=j+1 会把 nums[j] 自己算进左段、多配一个；漏写 hi 则整段都搜、越界到 j 右边。

复杂度上，排序 O(n log n) 是主要开销，n 个右端各做一次 O(log n) 二分，合起来仍是 O(n log n)。空间除下标计数器外 O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans = 0
        for j, x in enumerate(nums):
            i = bisect_left(nums, target - x, hi=j)
            ans += i
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int j = 0; j < nums.size(); ++j) {
            int i = lower_bound(nums.begin(), nums.begin() + j, target - nums[j]) - nums.begin();
            ans += i;
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int ans = 0;
        for (int j = 0; j < nums.size(); ++j) {
            int x = nums.get(j);
            int i = search(nums, target - x, j);
            ans += i;
        }
        return ans;
    }

    private int search(List<Integer> nums, int x, int r) {
        int l = 0;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums.get(mid) >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}