LeetCode 1885. Count Pairs in Two Arrays（二分查找）

Example 1:
Input: nums1 = [2,1,2,1], nums2 = [1,2,1,2]
Output: 1
Explanation: The pairs satisfying the condition are:
- (0, 2) where 2 + 2 > 1 + 1.

Example 2:
Input: nums1 = [1,10,6,2], nums2 = [1,4,1,5]
Output: 5
Explanation: The pairs satisfying the condition are:
- (0, 1) where 1 + 10 > 1 + 4.
- (0, 2) where 1 + 6 > 1 + 1.
- (1, 2) where 10 + 6 > 4 + 1.
- (1, 3) where 10 + 2 > 4 + 5.
- (2, 3) where 6 + 2 > 1 + 5.
 

Constraints:
n == nums1.length == nums2.length
1 <= n <= 10^5
1 <= nums1[i], nums2[i] <= 10^5

class Solution {
public:
    long long countPairs(vector<int>& nums1, vector<int>& nums2) {
        // 等价于 nums1[i]-nums2[i] > nums2[j]-nums1[j],  i < j
        // diff[i] + diff[j] > 0, i,j顺序调换也可以满足，所以只需 i!=j
        int n = nums1.size();
        vector<int> diff(n);
        for(int i = 0; i < n; ++i)
            diff[i] = nums1[i] - nums2[i];
        sort(diff.begin(), diff.end());
        long long ans = 0;
        for(int i = 0; i < n; ++i)
        {
            auto it = lower_bound(diff.begin(), diff.end(), -diff[i]+1);
            ans += diff.end()-it;//这么多数满足
            if(it <= diff.begin()+i)//包含了i，减 1
                ans--;
        }
        return ans/2; // i < j 有一半是重复的
    }
};