What is the recommended approach for counting pairs less than target?

Sorting the array and applying a two-pointer or binary search approach efficiently counts valid pairs while avoiding double-counting.

Can a brute-force solution pass this problem?

Yes, because the array length is at most 50, brute-force nested loops can compute the count correctly within acceptable time limits.

How do negative numbers affect pair counting?

Negative numbers can decrease sums, so sorting is important and binary search ensures you correctly capture all pairs less than the target.

Does the order of the array matter?

The original order does not affect the count as long as you check all i < j pairs; sorting simplifies the logic for efficient methods.

Which pattern does this problem exemplify?

This problem is a binary search over the valid answer space pattern, where each element's valid pairing range is found efficiently.

#2824

Easy

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

统计和小于目标的下标对数目

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 且 nums[i] + nums[j] 的下标对 (i, j) 的数目。示例 1：输入： nums = [-1,1,2,3,1], target = 2 输出： 3 解释：总共有 3 个下标…

数组双指针二分查找排序

题目描述

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。

示例 1：

输入：nums = [-1,1,2,3,1], target = 2
输出：3
解释：总共有 3 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
- (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target 
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target
注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。

示例 2：

输入：nums = [-6,2,5,-2,-7,-1,3], target = -2
输出：10
解释：总共有 10 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target
- (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target
- (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target
- (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target
- (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target
- (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target
- (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target
- (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target
- (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target

提示：

1 <= nums.length == n <= 50
-50 <= nums[i], target <= 50

lightbulb

解题思路

方法一：排序 + 二分查找

我们先对数组 $nums$ 进行排序，然后枚举 $j$ ，在 $[0, j)$ 的范围内使用二分查找第一个大于等于 $target - nums[j]$ 的下标 $i$ ，那么 $[0, i)$ 的范围内的所有下标 $k$ 都满足条件，因此答案增加 $i$ 。

遍历结束后，我们返回答案。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	complexity ranges from O(n^2) for brute-force to O(n log n) for sorting plus binary search per element. Space complexity is O(1) extra for pointers or O(n) if storing sorted array separately.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for solutions that avoid counting pairs multiple times.
question_mark
Consider if sorting can simplify pair comparisons.
question_mark
Check if binary search reduces the number of sum calculations per index.

warning

常见陷阱

外企场景

error
Forgetting to only count pairs where i < j, leading to overcounting.
error
Neglecting negative numbers and assuming all sums increase with indices.
error
Using inefficient brute-force for large arrays without noticing sorting opportunities.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count pairs whose sum is less than or equal to target.
arrow_right_alt
Count triplets with sum less than target using similar binary search logic.
arrow_right_alt
Return the actual list of valid pairs instead of just the count.

help

常见问题

外企场景

继续练习

#2576 求出最多标记下标 #2563 统计公平数对的数目 #3186 施咒的最大总伤害