# 2426. Number of Pairs Satisfying Inequality
###### tags: `Leetcode` `Hard` `Binary Search`
Link: https://leetcode.com/problems/number-of-pairs-satisfying-inequality/
## 思路
对比 [1885. Count Pairs in Two Arrays](https://hackmd.io/JJb56E1kTviOjH2qQcEE6A)
题目要求```nums1[i]-nums1[j]<=nums2[i]-nums2[j]+diff```
我们可以把它变成```nums1[i]-nums2[i]<=nums1[j]-nums2[j]+diff```
所以我们生成一个```nums1-nums2```array对于每一个```i```我们用binary search找到它前面所有小于```nums[i]+diff```的值的个数
## Code

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int diff) {
        int n = nums1.length;
        for(int i=0; i<n; i++) nums1[i] -= nums2[i];
        List<Integer> d = new ArrayList<>();
        long ans = 0;
        for(int i=0; i<n; i++){
            ans += binarySearch(d, nums1[i]+diff);
            d.add(binarySearch(d, nums1[i]), nums1[i]);
        }
        return ans;
    }
    private int binarySearch(List<Integer> d, int num){
        int start = 0;
        int end = d.size();
        while(start<end){
            int mid = start+(end-start)/2;
            if(d.get(mid)<=num){
                start = mid+1;
            }
            else end = mid;
        }
        return start;
    }
}