Description
Given two integer arrays nums1
and nums2
of length n
, count the pairs of indices (i, j)
such that i < j
and nums1[i] + nums1[j] > nums2[i] + nums2[j]
.
Return the number of pairs satisfying the condition.
Example 1:
Input: nums1 = [2,1,2,1], nums2 = [1,2,1,2]
Output: 1
Explanation: The pairs satisfying the condition are:
- (0, 2) where 2 + 2 > 1 + 1.
Example 2:
Input: nums1 = [1,10,6,2], nums2 = [1,4,1,5]
Output: 5
Explanation: The pairs satisfying the condition are:
- (0, 1) where 1 + 10 > 1 + 4.
- (0, 2) where 1 + 6 > 1 + 1.
- (1, 2) where 10 + 6 > 4 + 1.
- (1, 3) where 10 + 2 > 4 + 5.
- (2, 3) where 6 + 2 > 1 + 5.
Constraints:
n == nums1.length == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 105
Solutions
Solution 1
| class Solution:
def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
d = [nums1[i] - nums2[i] for i in range(n)]
d.sort()
return sum(n - bisect_right(d, -v, lo=i + 1) for i, v in enumerate(d))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public long countPairs(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] d = new int[n];
for (int i = 0; i < n; ++i) {
d[i] = nums1[i] - nums2[i];
}
Arrays.sort(d);
long ans = 0;
for (int i = 0; i < n; ++i) {
int left = i + 1, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (d[mid] > -d[i]) {
right = mid;
} else {
left = mid + 1;
}
}
ans += n - left;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public:
long long countPairs(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> d(n);
for (int i = 0; i < n; ++i) d[i] = nums1[i] - nums2[i];
sort(d.begin(), d.end());
long long ans = 0;
for (int i = 0; i < n; ++i) {
int j = upper_bound(d.begin() + i + 1, d.end(), -d[i]) - d.begin();
ans += n - j;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | func countPairs(nums1 []int, nums2 []int) int64 {
n := len(nums1)
d := make([]int, n)
for i, v := range nums1 {
d[i] = v - nums2[i]
}
sort.Ints(d)
var ans int64
for i, v := range d {
left, right := i+1, n
for left < right {
mid := (left + right) >> 1
if d[mid] > -v {
right = mid
} else {
left = mid + 1
}
}
ans += int64(n - left)
}
return ans
}
|