Leetcode 2563. Count the Number of Fair Pairs

[Woodyiiiiiii]

这道题是周赛第二题，按道理说不难，我却花了很长时间去解决。

首先，我的思路是，从左到右遍历数组，到某个位置i，要找到[0,i-1]之间位于[lower-nums[i], upper - nums[i]]的数的个数。我一开始把目光放到数身上，想用map之类的结构来定位，但显然失败了。这时想到用排序+二分，我可以对之前遍历过的元素排序，然后用二分找到上下界，然后求得范围内的个数。显然，这个方法的思路是根据lower和upper这两个条件来延伸。

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        long count = 0;
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            // find the number of num in the range of [lower - nums[i], upper - nums[i]] in lg(n) time
            int left = lower - num, right = upper - num;
            int leftIndex = bs1(list, left);
            int rightIndex = bs2(list, right);
            count += leftIndex >= 0 && rightIndex >= 0 && rightIndex >= leftIndex ? rightIndex - leftIndex + 1 : 0;
            // insert num into the list in lg(n) time
            int index = Collections.binarySearch(list, num);
            if (index < 0) {
                index = -index - 1;
            }
            list.add(index, num);
        }
        return count;
    }

    private int bs1(List<Integer> list, int left) {
        int l = 0, r = list.size();
        while (l < r) {
            int m = (l + r) >> 1;
            if (list.get(m) >= left) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

    private int bs2(List<Integer> list, int right) {
        int l = 0, r = list.size();
        while (l < r) {
            int m = (l + r) >> 1;
            if (list.get(m) <= right) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l - 1;
    }
}

此外，我们也可以用双指针来做。

首先，条件一中0<i<j<nums.length，让我第一个念头排除了对整个数组排序的思路，但是，看条件二是两个数相加的范围，所以i和j的先后顺序就不需要在意了。

整个数组排序后，我们定义两端指针l和r，l是用来遍历所有数组位置的，而r不需要每次都恢复最末端位置，因为l+1对于l来说，即然[l,r]小于数target后，那么l+1对应的r一定不能往右移动了。同样这是针对上下界限。

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        long ans = 0;
        Arrays.sort(nums);
        return bs(nums, upper) - bs(nums, lower - 1);
    }

    private long bs(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        long ans = 0L;
        while (l < r) {
            while (nums[l] + nums[r] > target && l < r) {
                --r;
            }
            ans += r - l;
            ++l;
        }
        return ans;
    }
}

Tips：

1. 数组之类的题目很多方面可以用到排序
2. 数组内找范围的题目，相关思路有：(1).排序(二分/双指针) (2) 树状数组

---

• 2563. Count the Number of Fair Pairs
• 1984. Minimum Difference Between Highest and Lowest of K Scores