DEV Community

Kardel Chen
Kardel Chen

Posted on

Leetcode 1885 Count Pairs in Two Arrays

class Solution {
    public long countPairs(int[] nums1, int[] nums2) {
        // We are counting i&j that ((nums1[i]-nums2[i])+(nums1[j]-nums2[j])>0)
        int N = nums1.length;
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = nums1[i] - nums2[i];
        }
        // sort that, then this question is like a 2Sum question.
        Arrays.sort(nums);
        long res = 0;
        // Use two pointers like 2Sum
        int i = 0;
        int j = nums.length - 1;
        while(j > i){
            // if nums[i] + nums[j] > 0, then (j-i) are all available results
            if(nums[i] + nums[j] > 0){
                res += j - i;
                j--;
            }else{
                // or increase i to try new value to make the sum larger
                i++;
            }
        }
        return res;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)