2563. Count the Number of Fair Pairs

解題思路

先假設 sort 好的 input = [0, 1, 4, 4, 5, 7]。很明顯不可能把 array  中任兩個數字的 pair 都檢查一次，這樣時間複雜度太高。

要簡化，直覺想到要調整 boundary，至少某些數字超過 upper 想也知道要排除掉。

用這個邏輯往下繼續想，其實可以用兩個 pointer 構成的boundary，找出當下有幾個符合的 pair。

譬如說當 left = 0, right = 4 時，代表數字 0 跟 1、4、4、5 都是可以選擇的組合，共有四個。

用這個方法找出所有 < upper 的 pair，在減掉其中 < lower 的組合即可。

程式碼

class Solution {
public:
    long long helper(vector<int>& nums, int bound)
    {
        long long ans = 0;
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            while(left < right && nums[left] + nums[right] > bound)
                right--;
            ans += right - left;
            left++;
        }
        return ans;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        return helper(nums, upper) - helper(nums, lower - 1);
    }
};