Hard

题目描述

给你两个下标从 0 开始的整数数组 nums1 和 nums2，两个数组的大小都为 n，同时给你一个整数 diff，统计满足以下条件的数对 (i, j) ：

  • 0 <= i < j <= n - 1 且
  • nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff

请你返回满足条件的数对数目。

示例 1：

输入：nums1 = [3,2,5], nums2 = [2,2,1], diff = 1
输出：3
解释：
总共有 3 个满足条件的数对：
1. i = 0, j = 1：3 - 2 <= 2 - 2 + 1 。由于 i < j 且 1 <= 1 ，这个数对满足条件。
2. i = 0, j = 2：3 - 5 <= 2 - 1 + 1 。由于 i < j 且 -2 <= 2 ，这个数对满足条件。
3. i = 1, j = 2：2 - 5 <= 2 - 1 + 1 。由于 i < j 且 -3 <= 2 ，这个数对满足条件。
因此，我们返回 3 。

示例 2：

输入：nums1 = [3,-1], nums2 = [-2,2], diff = -1
输出：0
解释：
由于不存在满足条件的数对，所以我们返回 0 。

提示：

  • n == nums1.length == nums2.length
  • 2 <= n <= 10^5
  • -10^4 <= nums1[i], nums2[i] <= 10^4
  • -10^4 <= diff <= 10^4

解题思路

解题思路

这道题的关键在于对不等式进行数学变换。原始条件是： nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff

通过移项可以得到： nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff

令 arr[k] = nums1[k] - nums2[k]，则条件变为： arr[i] <= arr[j] + diff

现在问题转化为：对于每个位置 j，统计在它前面有多少个位置 i 满足 arr[i] <= arr[j] + diff。

解法一：归并排序（推荐）

  • 使用分治思想，在归并过程中统计跨越左右两部分的满足条件的数对
  • 对于右半部分的每个元素，统计左半部分中小于等于它加上diff的元素个数

解法二：树状数组/线段树

  • 从右往左遍历数组，对于每个位置j，查询已处理元素中小于等于 arr[j] + diff 的个数
  • 需要先进行坐标压缩处理数值范围

解法三：有序集合

  • 使用支持范围查询的数据结构，从右往左处理元素

本题解采用归并排序解法，时间复杂度最优且实现相对简单。

代码实现

class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
        int n = nums1.size();
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            arr[i] = nums1[i] - nums2[i];
        }
        
        return mergeSort(arr, 0, n - 1, diff);
    }
    
private:
    long long mergeSort(vector<int>& arr, int left, int right, int diff) {
        if (left >= right) return 0;
        
        int mid = left + (right - left) / 2;
        long long count = mergeSort(arr, left, mid, diff) + mergeSort(arr, mid + 1, right, diff);
        
        // 统计跨越左右两部分的满足条件的数对
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && arr[i] <= arr[j] + diff) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // 归并
        vector<int> temp(right - left + 1);
        int i = left, k = 0;
        j = mid + 1;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        
        for (int i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
        
        return count;
    }
};

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:
        arr = [nums1[i] - nums2[i] for i in range(len(nums1))]
        
        def mergeSort(left, right):
            if left >= right:
                return 0
            
            mid = (left + right) // 2
            count = mergeSort(left, mid) + mergeSort(mid + 1, right)
            
            # 统计跨越左右两部分的满足条件的数对
            j = mid + 1
            for i in range(left, mid + 1):
                while j <= right and arr[i] <= arr[j] + diff:
                    j += 1
                count += j - (mid + 1)
            
            # 归并
            temp = []
            i, j = left, mid + 1
            while i <= mid and j <= right:
                if arr[i] <= arr[j]:
                    temp.append(arr[i])
                    i += 1
                else:
                    temp.append(arr[j])
                    j += 1
            
            while i <= mid:
                temp.append(arr[i])
                i += 1
            while j <= right:
                temp.append(arr[j])
                j += 1
            
            for i in range(len(temp)):
                arr[left + i] = temp[i]
            
            return count
        
        return mergeSort(0, len(arr) - 1)

public class Solution {
    public long NumberOfPairs(int[] nums1, int[] nums2, int diff) {
        int n = nums1.Length;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nums1[i] - nums2[i];
        }
        
        return MergeSort(arr, 0, n - 1, diff);
    }
    
    private long MergeSort(int[] arr, int left, int right, int diff) {
        if (left >= right) return 0;
        
        int mid = left + (right - left) / 2;
        long count = MergeSort(arr, left, mid, diff) + MergeSort(arr, mid + 1, right, diff);
        
        // 统计跨越左右两部分的满足条件的数对
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && arr[i] <= arr[j] + diff) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // 归并
        int[] temp = new int[right - left + 1];
        int idx1 = left, idx2 = mid + 1, k = 0;
        while (idx1 <= mid && idx2 <= right) {
            if (arr[idx1] <= arr[idx2]) {
                temp[k++] = arr[idx1++];
            } else {
                temp[k++] = arr[idx2++];
            }
        }
        while (idx1 <= mid) temp[k++] = arr[idx1++];
        while (idx2 <= right) temp[k++] = arr[idx2++];
        
        for (int i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
        
        return count;
    }
}

var numberOfPairs = function(nums1, nums2, diff) {
    const n = nums1.length;
    const arr = nums1.map((val, i) => val - nums2[i]);
    
    function mergeSort(left, right) {
        if (left >= right) return 0;
        
        const mid = Math.floor((left + right) / 2);
        let count = mergeSort(left, mid) + mergeSort(mid + 1, right);
        
        // 统计跨越左右两部分的满足条件的数对
        let j = mid + 1;
        for (let i = left; i <= mid; i++) {
            while (j <= right && arr[i] <= arr[j] + diff) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // 归并
        const temp = [];
        let i = left;
        j = mid + 1;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp.push(arr[i++]);
            } else {
                temp.push(arr[j++]);
            }
        }
        while (i <= mid) temp.push(arr[i++]);
        while (j <= right) temp.push(arr[j++]);
        
        for (let i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
        
        return count;
    }
    
    return mergeSort(0, n - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型归并排序解法树状数组解法
时间复杂度O(n log n)O(n log n)
空间复杂度O(n)O(n)

相关题目