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
}