/
CountNumberOfFairPairs.java
64 lines (53 loc) · 1.78 KB
/
CountNumberOfFairPairs.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// https://leetcode.com/problems/count-the-number-of-fair-pairs
class Solution {
public long countFairPairs(int[] nums, int lower, int upper) {
long count = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
int min = lower - nums[i];
int max = upper - nums[i];
int buff = 0;
if (max < nums[i]) {
continue;
}
int minIx = Arrays.binarySearch(nums, i + 1, nums.length, min);
int maxIx = Arrays.binarySearch(nums, i + 1, nums.length, max);
if (minIx < 0) {
minIx = -minIx - 1;
} else {
minIx = getExtremePosition(nums, min, minIx, i, 0);
buff = 1;
}
if (maxIx < 0) {
maxIx = -maxIx - 1;
while (nums[--maxIx] > max);
buff = 1;
} else {
maxIx = getExtremePosition(nums, max, maxIx, i, 1);
buff = 1;
}
count += maxIx - minIx + buff;
}
return count;
}
int getExtremePosition(int[] nums, int val, int currIx, int i, int dir) {
int pos = -1, lastPos = currIx;
if (currIx > 0 && currIx < nums.length - 1) {
if (nums[currIx + (dir == 0 ? -1 : 1)] != val) {
return currIx;
}
}
while (true) {
if (dir == 0) {
pos = Arrays.binarySearch(nums, i + 1, lastPos + 1, val);
} else {
pos = Arrays.binarySearch(nums, lastPos + 1, nums.length, val);
}
if (pos < 0 || nums[pos] != val || lastPos == pos) {
break;
}
lastPos = pos;
}
return lastPos;
}
}