# LeetCode 2563. Count the Number of Fair Pairs

https://leetcode.com/problems/count-the-number-of-fair-pairs/description/

## 題目大意

給定整數陣列 `nums` 以及兩整數 `lower` 跟 `upper`
定義 `(i, j)` 為 fair pair 若且唯若：

1. $0\le i\lt j\lt\text{nums.length}$
2. $\text{lower}\le \text{nums}\left[ i \right] + \text{nums}\left[ j \right]\le\text{upper}$

## 思考

這題有個小關鍵就是 `nums[i] + nums[j] == nums[j] + nums[i]` 這件事
換句話說，我們的檢查條件可以從 `i < j` 變成 `i != j`

我們可以放心對 `nums` 做排序
假設我們知道所有總和不超過 `upper` 的 pair 數，將其扣除不超過 `lower - 1` 的 pair 數，即為所求

C++ 參考解答：

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

private:
    long long countNotGreater(const vector<int> &nums, int target)
    {
        long long ans = 0;
        for (auto begin = nums.begin(), end = prev(nums.end()); begin < end; ++begin)
        {
            while (begin < end && *begin + *end > target)
                --end;
            ans += end - begin;
        }

        return ans;
    }
};

Go 參考解答：

func countFairPairs(nums []int, lower int, upper int) int64 {
	sort.Ints(nums)
	return countNotGreater(nums, upper) - countNotGreater(nums, lower-1)
}

func countNotGreater(nums []int, target int) (ans int64) {
	start, end := 0, len(nums)-1

	for start < end {
		if nums[start]+nums[end] > target {
			end--
		} else {
			ans += int64(end - start)
			start++
		}
	}

	return
}