2563. Count the Number of Fair Pairs

2563. Count the Number of Fair Pairs
Solved
Medium
Topics
Companies
Hint
Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

0 <= i < j < n, and
lower <= nums[i] + nums[j] <= upper

---

접근

 

lower, upper 값 사이에서 pair ( x + y ) 값으로 구성 가능한 조합의 갯수를 찾아야 합니다.

i, j 각각 순회를 돌면서 답을 찾는 방법은 O ( N ^ 2 ) 을 사용하며 시간 초과가 발생합니다.

 

sort 를 사용하여 O ( N * logN )

i 번째 element 를 사용하여 나머지 j 번째 element 는 lower, upper 내 index 차이로 갯수를 계산합니다.

---

코드

/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var countFairPairs = function (nums, lower, upper) {
    // sort
    nums.sort((a, b) => a - b);

    var len = nums.length;

    var pairs = 0;
    for (var i = 0; i < len - 1; i++) {
        var p = nums[i];
        var min = lower - p, max = upper - p;

        var min_i = i + 1, max_i = len - 1;

        // invalid case
        if (max < nums[min_i] || nums[max_i] < min) continue;

        // find lower bound
        var min_n = find_bound(min_i, max_i, min, true);
        // find upper bound
        var max_n = find_bound(min_i, max_i, max, false);

        pairs += (max_n - min_n) + 1;
    }

    return pairs;

    function find_bound(i, j, v, is_lower) {
        var left = i, right = j;
        // binary search
        while (left <= right) {
            var mid = Math.floor((left + right) / 2);
            var mid_n = nums[mid];
            // found
            if (mid_n == v) {
                if (is_lower) {
                    // slice when same value
                    for (var k = mid - 1; k >= i; k--) {
                        if (nums[k] == v) {
                            mid = k;
                        } else {
                            break;
                        }
                    }
                } else {
                    // slice when same value
                    for (var k = mid + 1; k <= j; k++) {
                        if (nums[k] == v) {
                            mid = k;
                        } else {
                            break;
                        }
                    }
                }

                return mid;
            }
            else if (mid_n > v) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        // fail to find
        if (is_lower) {
            // set lower
            return nums[left] >= v ? left : left + 1;
        }
        else {
            // set upper
            return nums[right] <= v ? right : right - 1;
        }
    }
};