题目描述
给你一个下标从 0 开始长度为 n
的整数数组 nums
和一个整数 target
,请你返回满足 0 <= i < j < n
且 nums[i] + nums[j] < target
的下标对 (i, j)
的数目。
样例
输入: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。
输入: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
算法1
(暴力枚举) $O(n^2)$
- 按照题目描述两重循环枚举下标对,并累加答案。
时间复杂度
- 两重循环,故时间复杂度为 $O(n^2)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int countPairs(vector<int>& nums, int target) {
const int n = nums.size();
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (nums[i] + nums[j] < target)
++ans;
return ans;
}
};
算法2
(树状数组) $O(n \log m)$
- 定义树状数组,存储数字的出现次数,维护前缀和。
- 遍历数组,每次在树状数组中查询小于等于 $target - nums(i) - 1$ 数字的个数累加答案,然后将当前数字插入树状数组中。
- 由于存在负数,则树状数组需要 $O = 101$ 的偏移量平移数字。
时间复杂度
- 树状数组单次查询或插入的时间复杂度为 $O(\log m)$,其中 $m$ 为数字的最大值。
- 共操作 $2n$ 次树状数组,故时间复杂度为 $O(n \log m)$。
空间复杂度
- 需要 $O(m)$ 的额外空间存储树状数组。
C++ 代码
const int N = 210, O = 101;
class Solution {
private:
int f[N];
int query(int x) {
int tot = 0;
for (; x; x -= x & -x)
tot += f[x];
return tot;
}
void add(int x, int y) {
for (; x < N; x += x & -x)
f[x] += y;
}
public:
int countPairs(vector<int>& nums, int target) {
const int n = nums.size();
int ans = 0;
for (int i = 0; i < n; i++) {
ans += query(target - nums[i] - 1 + O);
add(nums[i] + O, 1);
}
return ans;
}
};