diff options
Diffstat (limited to 'count_num_fair_pairs.c')
-rw-r--r-- | count_num_fair_pairs.c | 51 |
1 files changed, 15 insertions, 36 deletions
diff --git a/count_num_fair_pairs.c b/count_num_fair_pairs.c index 80d26f1..9ddfc9a 100644 --- a/count_num_fair_pairs.c +++ b/count_num_fair_pairs.c @@ -7,46 +7,25 @@ * i < j < n' and 'lower <= nums[i] + nums[j] <= upper' */ -int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } - -int bs_lower(int *nums, int n, int left, int right, int lower) { - int l = left, r = right; - if (nums[r] < lower) - return -1; - while (l < r) { - int m = l + (r - l) / 2; - if (nums[m] < lower) - l = m + 1; - else - r = m; - } - return l; -} - -int bs_upper(int *nums, int n, int left, int right, int upper) { - int l = left, r = right; - if (nums[l] > upper) - return -1; - while (l < r) { - int m = r - (r - l) / 2; - if (nums[m] > upper) - r = m - 1; - else - l = m; - } - return l; +int cmp(const void *a, const void *b) { + return (*(int *)a > *(int *)b) - (*(int *)b > *(int *)a); } long long countFairPairs(int *nums, int numsSize, int lower, int upper) { - int n = numsSize; + qsort(nums, numsSize, sizeof(int), cmp); long long ans = 0; - qsort(nums, n, sizeof(int), cmp); - for (int i = 0; i < n - 1; i++) { - int left = bs_lower(nums, n, i + 1, n - 1, lower - nums[i]); - int right = bs_upper(nums, n, i + 1, n - 1, upper - nums[i]); - if (left != -1 && right != -1) - ans += right - left + 1; - } + int i = 0, j = numsSize - 1; + while (i < j) + if (nums[i] + nums[j] < lower) + ans -= j - i++; + else + j--; + i = 0, j = numsSize - 1; + while (i < j) + if (nums[i] + nums[j] <= upper) + ans += j - i++; + else + j--; return ans; } |