문제 링크

내 코드

• 약간의 착오.
  • 정렬 후 binary search할 때 중복 탐색하지 않음.
• 추가 링크
  • https://leetcode.com/explore/learn/card/binary-search/

• binary search
• 71ms, 60.4MB

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        // index 신경 쓸 필요가 없구나 (어차피 중복 카운팅 안 됨.)
        sort(begin(nums), end(nums));

        long long answer{};
        // lower - *it <= nums[j] <= upper -*it
        // lower - *it <= nums[j] < upper + 1 - *it 
        for(auto it = begin(nums); it!=end(nums);++it) {
            // [s, e)
            auto s = lower_bound(it + 1, end(nums), lower - *it);
            auto e = lower_bound(it + 1, end(nums), upper + 1 - *it);
            answer += e - s;
        }

        return answer;
    }
};

Solution

Approach 1: Binary Search

• 63ms, 60.36MB
• Complexity
  • Let n be the size of the given nums array.
  • Time Complexity: $O(n \log n)$
  • Space Complexity: $O(\log n)$
    • C++: sort() $\Rightarrow$ as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worse-case space complexity of $O(\log n)$.

class Solution {
public:
    long long lower_bound(vector<int>& nums, int low, int high, int element) {
        while (low <= high) {
            int mid = low + ((high - low) / 2);
            if (nums[mid] >= element) {
                high = mid - 1;
            } else
                low = mid + 1;
        }
        return low;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        long long ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            // Assume we have picked nums[i] as the first pair element.

            // `low` indicates the number of possible pairs with sum < lower.
            int low =
                lower_bound(nums, i + 1, nums.size() - 1, lower - nums[i]);

            // `high` indicates the number of possible pairs with sum <= upper.
            int high =
                lower_bound(nums, i + 1, nums.size() - 1, upper - nums[i] + 1);

            // Their difference gives the number of elements with sum in the
            // given range.
            ans += 1LL * (high - low);
        }
        return ans;
    }
};

Approach 2: Two Pointers

• 21ms, 60.44MB
• Complexity
  • Let n be the size of the given nums array.
  • Time Complexity: $O(n \log n)$
  • Space Complexity: $O(\log n)$
    • C++: sort() $\Rightarrow$ as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worse-case space complexity of $O(\log n)$.

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        return lower_bound(nums, upper + 1) - lower_bound(nums, lower);
    }

private:
    long long lower_bound(vector<int>& nums, int value) {
        int left = 0, right = nums.size() - 1;
        long long result = 0;
        while (left < right) {
            int sum = nums[left] + nums[right];
            // If sum is less than value, add the size of window to result and
            // move to the next index.
            if (sum < value) {
                result += (right - left);
                left++;
            } else {
                // Otherwise, shift the right pointer backwards, until we get a
                // valid window.
                right--;
            }
        }
        return result;
    }
};