My fucked up emotion & LeetCode-2426.满足不等式的数对数目-hard

无感少年🧚‍♂️

如果要用两个字来描述我整个9月份的状态，那么我用屁股想也能毫不费力蹦出两个字“躺平”。若是换个精确的词，也许“无感”是最合适标签化我最近一段时间行为状态的词…唔，也许时间线能拉的更长。

大概总结这月干了啥**”无感的正事”**吧：(1) 随意性阅读论文。这段时间似乎没带任何功利的想法阅读论文，涉及论文领域的广度也蛮宽泛，譬如ABSA、prompt learning、few shot learning、humor detection、chain of thought。这样做给我带来的反馈几乎为0，也没有得到任何灵感一闪的idea，但似乎我对这种低效并无任何不适的感觉😅…… (2) 准备汇报。一是学校大研讨会主讲，二是参与国际会议演讲。以我对自己性格的了解，一旦得知我需要上台作presentation的时候一定会强行push自己（提前把PPT做出来，反复打磨十几二十遍，设置好展示过程中每一处的转折和强调）。好嘛…到现在我还没把PPT搞好，反倒是强行pull自己躺了大半个月😅……

今年，无感顽强活跃于我生活的处处细节：自驾游无感，美食无感，拿offer无感，paper被accept无感，奖学金无感，打比赛AK无感，跟喜欢的人打交道无感，篮球炸场无感，爱无感……

有天我甚至在想，当对所有事物无感时我还是人吗？ 但谁又能说明白无感是否为人的一种特有情感呢？我应该抑制无感野蛮生长吗？

也许，往后我需要一段时间自我认知和剖析才能给出答案。

---

如果问我这世界上最优美的数据结构是什么，树状数组永远不会缺席（英文：BIT, binary indexed trees）。

题目

给你两个下标从 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

题解

【问题转化🎈🎈】

        - 令a[i] = nums1[i]-nums2[i]
        - 问题转化成求在数组a范围内满足以下条件的数对(i， j)，满足 a[i] <= a[j] + diff 且 i < j

【问题求解——暴力🙅‍♀️】

        - 在原数组a中从前往后求解小于等于a[i]+diff的元素个数
        - 从前往后遍历数组a需要O(n)， 求解答案也需要遍历a数组， 总时间复杂度O(n^2)。由于数据范围上限为10^5，因此会超时

【问题求解——树状数组🙋‍♀️】

        - query: 在树状数组tr中求解小于等于a[i]+diff的元素个数
        - add: 将当前a[i]插入树状数组中，值为1表示累计a[i]出现1次
        - 从前往后遍历数组a需要O(n)， 而query和add需要O(logn)， 总时间复杂度为O(n*logn)

树状数组不会？点我🤗

class Solution {
    int offset = 3*10000;    // 由于num1[i] - num2[i] + diff 最小可以达到3*10000,所以需要偏移才能使得下标大于0
    int n = offset*2+10;
    
    /* 树状数组模板 */
    int[] tr = new int[n];

    public int lowbit(int x){
        return x & (-x);
    }

    public void add(int x, int val){
        while(x < n){
            tr[x] += val;
            x += lowbit(x);
        }
    }

    public int query(int x){
        int res = 0;
        while(x > 0){
            res += tr[x];
            x -= lowbit(x);
        }
        return res;
    }
    /* 树状数组模板 */

    public long numberOfPairs(int[] nums1, int[] nums2, int diff) {
        int n = nums1.length;
        long ans = 0;
        for(int i=0;i<n;i++){
            ans += query(nums1[i] - nums2[i] + offet + diff);
            add(nums1[i] - nums2[i] + offet, 1);
        }
        return ans;
    }
}

树状数组相关题目

• Leetcode
  • 303 区域和检索 - 数组不可变
  • 307 区域和检索 - 数组可修改

赏

谢谢你请我吃糖果