❌

阅读视图

发现新文章，点击刷新页面。

每日一题-统计公平数对的数目🟡

✇LeetCode 每日一题题解

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

  • 0 <= i < j < n，且
  • lower <= nums[i] + nums[j] <= upper

 

示例 1：

输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。

示例 2：

输入：nums = [1,7,9,2,5], lower = 11, upper = 11
输出：1
解释：只有单个公平数对：(2,3) 。

 

提示：

  • 1 <= nums.length <= 105
  • nums.length == n
  • -109 <= nums[i] <= 109
  • -109 <= lower <= upper <= 109

真实双百解法：排序O(nlogn)+双指针O(n) Python || C++

✇LeetCode 每日一题题解
si-gu-wo-hai-zai

语言：Python3
提交时间：2023.02.15 20:27
时间：200 ms，击败97.7%
内存：26.3 MB，击败98.11%

解题思路

排序：不影响数目
原问题等价于<=upper的数对数目减去<=lower - 1的数对数目
left向右移动，统计每次nums[left] + nums[i] <= k的数目，总和即为res
right移至 nums[left] + nums[right] <= k 处，那么下标从left + 1到right的数 + nums[left]都是 <= k 的
易知left向右移后，满足条件的right需要左移或不动

以下代码易懂~

代码

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        n = len(nums)
        nums.sort()

        def my_count(k):  # 统计 <= k 的数对数目，原问题等价于 <=upper 的数对数目减去 <=lower - 1 的数对数目
            res = 0
            left, right = 0, n - 1
            while left < right:
                t = nums[left] + nums[right]
                if t <= k:  # 达到统计条件
                    res += right - left  
                  # 如果 nums[left] + nums[right] <= k, 那么下标从left + 1到right的数 + nums[left]都是 <= k 的
                    left += 1
                  # 继续统计 nums[left + 1] + nums[i] <= k 的数对
                else: # right指针左移，使t减小
                    right -= 1
            return res

        return my_count(upper) - my_count(lower - 1)

class Solution {
    // 统计 <= k 的数对数目，原问题等价于 <=upper 的数对数目减去 <=lower - 1 的数对数目
    long long my_count(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        long long res = 0;
        while (left < right) {
            int t = nums[left] + nums[right];
            if (t <= k) {  // 达到统计条件
                res += right - left;
            // 如果 nums[left] + nums[right] <= k, 那么下标从left + 1到right的数 + nums[left]都是 <= k 的
                left++;
            //  继续统计 nums[left + 1] + nums[i] <= k 的数对
            }
            else 
                right--;  // right指针左移，使t减小
        }
        return res;
    }
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        return my_count(nums, upper) - my_count(nums, lower - 1);
    }
};

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        n = len(nums)
        nums.sort()

        def my_count(k):
            res = 0
            left, right = 0, n - 1
            while left < right:
                t = nums[left] + nums[right]
                if t <= k:
                    res += right - left  
                    left += 1
                else:
                    right -= 1
            return res

        return my_count(upper) - my_count(lower - 1)

class Solution {
    long long my_count(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        long long res = 0;
        while (left < right) {
            int t = nums[left] + nums[right];
            if (t <= k) {
                res += right - left;
                left++;
            }
            else 
                right--;
        }
        return res;
    }
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        return my_count(nums, upper) - my_count(nums, lower - 1);
    }
};

题外话：为什么有人说用双指针超时了？ 答：

“双指针”O(n)需要保证的是，left和right指针只往1个方向移动，两种情况：

1、同向双指针，假设方向向右，right往右移，left跟在right后面，相当于O(2n)，“滑动窗口”那些题就是这个类型。
2、反向双指针，0和n-1移动至相遇。

如果某个指针，既会向左又会向右移，或者反复“移动后又移回原位”，那么最坏情况就是O(n²)，本质上还是两层for循环的暴力，做的优化相当于“剪枝”。

本题因为需要同时兼顾>=lower和<=upper，所以导致某个指针有时需要移动回去。这个时候我们把上下界问题等价于：<=upper的情况减去<=lower-1的情况 就可以了。

C++，排序，双指针

✇LeetCode 每日一题题解
yan-hua-yi-leng-iw

对于满足条件区间[i,j]的问题，我们一般转换成满足区间x<i-1和x<=j，然后将两个区间求得的结果相减。

我们先将nums排序，然后参考两数之和的双指针的操作，寻找在符合要求的范围内的两个边界。边界的长度-1就是当前边界中符合要求的对数，然后从左右向中间减小边界，重复上述操作，直到左右指针相碰。

例如：nums是[1,2,3,4,5,6],上界为8，那么开始时left指针指向1，right指向6，此时nums[left]+nums[right]<8,那么这个范围内所有的数都符合要求。接着left指针右移，直到nums[left]=3时，nums[left]+nums[right]>8，就移动right指针。

class Solution {
    long long count(vector<int> &nums, int upper)
    {
        int n = nums.size(), left = 0, right = n - 1;
        long long res = 0;
        while (left < right)//最后只剩一个数不能成对
        {
            long long sum = nums[left] + nums[right];
            if (sum <= upper)//判断当前双指针之和是否大于上界
            {   //不是的话，此范围内所有数都满足要求，范围内的对数为right-left
                res += right - left;
                left++;
            }
            else//如果大于上界，则right指针左移，sum会随之减小
                right--;
        }
        return res;
    }
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        int n=nums.size(),left=0,right=n-1;
        sort(nums.begin(),nums.end());
        long long small=count(nums,lower-1);
        long long big=count(nums,upper);
        return big-small;
    }
};

两种方法：二分查找 / 相向三指针（Python/Java/C++/C/Go/JS/Rust）

✇LeetCode 每日一题题解
endlesscheng

方法一：排序 + 二分查找

由于排序不影响答案，可以先（从小到大）排序，这样可以二分查找。

$\textit{nums}$ 是 $[1,2,3]$ 还是 $[3,2,1]$，算出来的答案都是一样的，本质上就是从 $\textit{nums}$ 中选两个数。

排序后，枚举 $\textit{nums}[j]$，那么 $\textit{nums}[i]$ 需要满足 $0\le i < j$ 以及

$$
\textit{lower} - \textit{nums}[j] \le \textit{nums}[i] \le \textit{upper} - \textit{nums}[j]
$$

计算 $\le \textit{upper} - \textit{nums}[j]$ 的元素个数，减去 $< \textit{lower} - \textit{nums}[j]$ 的元素个数，即为满足上式的元素个数。（联想一下前缀和）

由于 $\textit{nums}$ 是有序的，我们可以在 $[0,j-1]$ 中二分查找，原理见【基础算法精讲 04】：

  • 找到 $> \textit{upper} - \textit{nums}[j]$ 的第一个数，设其下标为 $r$，那么下标在 $[0,r-1]$ 中的数都是 $\le \textit{upper} - \textit{nums}[j]$ 的，这有 $r$ 个。如果 $[0,j-1]$ 中没有找到这样的数，那么二分结果为 $j$。这意味着 $[0,j-1]$ 中的数都是 $\le \textit{upper} - \textit{nums}[j]$ 的，这有 $j$ 个。
  • 找到 $\ge \textit{lower} - \textit{nums}[j]$ 的第一个数，设其下标为 $l$，那么下标在 $[0,l-1]$ 中的数都是 $< \textit{lower} - \textit{nums}[j]$ 的，这有 $l$ 个。如果 $[0,j-1]$ 中没有找到这样的数，那么二分结果为 $j$。这意味着 $[0,j-1]$ 中的数都是 $< \textit{lower} - \textit{nums}[j]$ 的，这有 $j$ 个。
  • 满足 $\textit{lower} - \textit{nums}[j] \le \textit{nums}[i] \le \textit{upper} - \textit{nums}[j]$ 的 $\textit{nums}[i]$ 的个数为 $r-l$，加入答案。
class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        ans = 0
        for j, x in enumerate(nums):
            # 注意要在 [0, j-1] 中二分，因为题目要求两个下标 i < j
            r = bisect_right(nums, upper - x, 0, j)
            l = bisect_left(nums, lower - x, 0, j)
            ans += r - l  
        return ans

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        long ans = 0;
        for (int j = 0; j < nums.length; j++) {
            // 注意要在 [0, j-1] 中二分，因为题目要求两个下标 i < j
            int r = lowerBound(nums, j, upper - nums[j] + 1);
            int l = lowerBound(nums, j, lower - nums[j]);
            ans += r - l;
        }
        return ans;
    }

    // 原理请看 https://www.bilibili.com/video/BV1AP41137w7/
    private int lowerBound(int[] nums, int right, int target) {
        int left = -1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        ranges::sort(nums);
        long long ans = 0;
        for (int j = 0; j < nums.size(); j++) {
            // 注意要在 [0, j-1] 中二分，因为题目要求两个下标 i < j
            auto r = upper_bound(nums.begin(), nums.begin() + j, upper - nums[j]);
            auto l = lower_bound(nums.begin(), nums.begin() + j, lower - nums[j]);
            ans += r - l;
        }
        return ans;
    }
};

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

// 原理请看 https://www.bilibili.com/video/BV1AP41137w7/
int lowerBound(int* nums, int right, int target) {
    int left = -1;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return right;
}

long long countFairPairs(int* nums, int numsSize, int lower, int upper) {
    qsort(nums, numsSize, sizeof(int), cmp);
    long long ans = 0;
    for (int j = 0; j < numsSize; j++) {
        // 注意要在 [0, j-1] 中二分，因为题目要求两个下标 i < j
        int r = lowerBound(nums, j, upper - nums[j] + 1);
        int l = lowerBound(nums, j, lower - nums[j]);
        ans += r - l;
    }
    return ans;
}

func countFairPairs(nums []int, lower, upper int) (ans int64) {
    slices.Sort(nums)
    for j, x := range nums {
        // 注意要在 [0, j-1] 中二分，因为题目要求两个下标 i < j
        r := sort.SearchInts(nums[:j], upper-x+1)
        l := sort.SearchInts(nums[:j], lower-x)
        ans += int64(r - l)
    }
    return
}

var countFairPairs = function(nums, lower, upper) {
    nums.sort((a, b) => a - b);
    let ans = 0;
    for (let j = 0; j < nums.length; j++) {
        // 注意要在 [0, j-1] 中二分，因为题目要求两个下标 i < j
        const r = lowerBound(nums, j, upper - nums[j] + 1);
        const l = lowerBound(nums, j, lower - nums[j]);
        ans += r - l;
    }
    return ans;
};

// 原理请看 https://www.bilibili.com/video/BV1AP41137w7/
var lowerBound = function(nums, right, target) {
    let left = -1;
    while (left + 1 < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return right;
};

impl Solution {
    pub fn count_fair_pairs(mut nums: Vec<i32>, lower: i32, upper: i32) -> i64 {
        nums.sort_unstable();
        let mut ans = 0;
        for j in 0..nums.len() {
            // 注意要在 [0, j-1] 中二分，因为题目要求两个下标 i < j
            let l = nums[..j].partition_point(|&x| x < lower - nums[j]);
            let r = nums[..j].partition_point(|&x| x <= upper - nums[j]);
            ans += r - l;
        }
        ans as _
    }
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 为 $\textit{nums}$ 的长度。
  • 空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

方法二：排序 + 相向三指针

由于随着 $\textit{nums}[j]$ 的变大，$\textit{upper}-\textit{nums}[j]$ 和 $\textit{lower} - \textit{nums}[j]$ 都在变小，有单调性，可以用相向三指针 $j,l,r$ 代替方法一中的二分查找：

  1. 初始化 $l=r=n$。
  2. 从左到右遍历（排序后的）$\textit{nums}$。
  3. 找 $> \textit{upper} - \textit{nums}[j]$ 的第一个数：如果 $\textit{nums}[r-1] > \textit{upper}-\textit{nums}[j]$，说明 $r$ 太大了，可以继续减小。循环结束后的 $r$，与 $j$ 取最小值后，就是方法一的二分查找计算出的 $r$。
  4. 找 $\ge \textit{lower} - \textit{nums}[j]$ 的第一个数：如果 $\textit{nums}[l-1] \ge \textit{lower}-\textit{nums}[j]$，说明 $l$ 太大了，可以继续减小。循环结束后的 $l$，与 $j$ 取最小值后，就是方法一的二分查找计算出的 $l$。
class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        ans = 0
        l = r = len(nums)
        for j, x in enumerate(nums):
            while r and nums[r - 1] > upper - x:
                r -= 1
            while l and nums[l - 1] >= lower - x:
                l -= 1
            # 在方法一中，二分的结果必须 <= j，方法二同理
            ans += min(r, j) - min(l, j)
        return ans

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        long ans = 0;
        int l = nums.length;
        int r = nums.length;
        for (int j = 0; j < nums.length; j++) {
            while (r > 0 && nums[r - 1] > upper - nums[j]) {
                r--;
            }
            while (l > 0 && nums[l - 1] >= lower - nums[j]) {
                l--;
            }
            // 在方法一中，二分的结果必须 <= j，方法二同理
            ans += Math.min(r, j) - Math.min(l, j);
        }
        return ans;
    }
}

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        ranges::sort(nums);
        long long ans = 0;
        int l = nums.size(), r = l;
        for (int j = 0; j < nums.size(); j++) {
            while (r && nums[r - 1] > upper - nums[j]) {
                r--;
            }
            while (l && nums[l - 1] >= lower - nums[j]) {
                l--;
            }
            // 在方法一中，二分的结果必须 <= j，方法二同理
            ans += min(r, j) - min(l, j);
        }
        return ans;
    }
};

#define MIN(a, b) ((b) < (a) ? (b) : (a))

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

long long countFairPairs(int* nums, int numsSize, int lower, int upper) {
    qsort(nums, numsSize, sizeof(int), cmp);
    long long ans = 0;
    int l = numsSize, r = numsSize;
    for (int j = 0; j < numsSize; j++) {
        while (r && nums[r - 1] > upper - nums[j]) {
            r--;
        }
        while (l && nums[l - 1] >= lower - nums[j]) {
            l--;
        }
        // 在方法一中，二分的结果必须 <= j，方法二同理
        ans += MIN(r, j) - MIN(l, j);
    }
    return ans;
}

func countFairPairs(nums []int, lower, upper int) (ans int64) {
    slices.Sort(nums)
    l, r := len(nums), len(nums)
    for j, x := range nums {
        for r > 0 && nums[r-1] > upper-x {
            r--
        }
        for l > 0 && nums[l-1] >= lower-x {
            l--
        }
        // 在方法一中，二分的结果必须 <= j，方法二同理
        ans += int64(min(r, j)-min(l, j))
    }
    return
}

var countFairPairs = function(nums, lower, upper) {
    nums.sort((a, b) => a - b);
    let ans = 0, l = nums.length, r = nums.length;
    for (let j = 0; j < nums.length; j++) {
        while (r && nums[r - 1] > upper - nums[j]) {
            r--;
        }
        while (l && nums[l - 1] >= lower - nums[j]) {
            l--;
        }
        // 在方法一中，二分的结果必须 <= j，方法二同理
        ans += Math.min(r, j) - Math.min(l, j);
    }
    return ans;
};

impl Solution {
    pub fn count_fair_pairs(mut nums: Vec<i32>, lower: i32, upper: i32) -> i64 {
        nums.sort_unstable();
        let mut ans = 0;
        let mut l = nums.len();
        let mut r = nums.len();
        for (j, &x) in nums.iter().enumerate() {
            while r > 0 && nums[r - 1] > upper - x {
                r -= 1;
            }
            while l > 0 && nums[l - 1] >= lower - x {
                l -= 1;
            }
            // 在方法一中，二分的结果必须 <= j，方法二同理
            ans += r.min(j) - l.min(j);
        }
        ans as _
    }
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 为 $\textit{nums}$ 的长度。瓶颈在排序上。
  • 空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
  7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

[Python3/Java/C++/Go/TypeScript] 一题一解：式子转换 + 哈希表（清晰题解）

✇LeetCode 每日一题题解
lcbin

方法一：式子转换 + 哈希表

根据题目描述，我们可以得知，对于任意的 $i \lt j$，如果 $j - i \neq \textit{nums}[j] - \textit{nums}[i]$，则 $(i, j)$ 是一个坏数对。

我们可以将式子转换为 $i - \textit{nums}[i] \neq j - \textit{nums}[j]$。这启发我们用哈希表 $cnt$ 来统计 $i - \textit{nums}[i]$ 的出现次数。

遍历数组，对于当前元素 $\textit{nums}[i]$，我们将 $i - cnt[i - \textit{nums}[i]]$ 加到答案中，然后将 $i - \textit{nums}[i]$ 的出现次数加 $1$。

最后，我们返回答案即可。

###python

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        cnt = Counter()
        ans = 0
        for i, x in enumerate(nums):
            ans += i - cnt[i - x]
            cnt[i - x] += 1
        return ans

###java

class Solution {
    public long countBadPairs(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        long ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            int x = i - nums[i];
            ans += i - cnt.merge(x, 1, Integer::sum) + 1;
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        unordered_map<int, int> cnt;
        long long ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int x = i - nums[i];
            ans += i - cnt[x]++;
        }
        return ans;
    }
};

###go

func countBadPairs(nums []int) (ans int64) {
cnt := map[int]int{}
for i, x := range nums {
x = i - x
ans += int64(i - cnt[x])
cnt[x]++
}
return
}

###ts

function countBadPairs(nums: number[]): number {
    const cnt = new Map<number, number>();
    let ans = 0;
    for (let i = 0; i < nums.length; ++i) {
        const x = i - nums[i];
        ans += i - (cnt.get(x) ?? 0);
        cnt.set(x, (cnt.get(x) ?? 0) + 1);
    }
    return ans;
}

###rust

use std::collections::HashMap;

impl Solution {
    pub fn count_bad_pairs(nums: Vec<i32>) -> i64 {
        let mut cnt: HashMap<i32, i64> = HashMap::new();
        let mut ans: i64 = 0;
        for (i, &num) in nums.iter().enumerate() {
            let x = i as i32 - num;
            let count = *cnt.get(&x).unwrap_or(&0);
            ans += i as i64 - count;
            *cnt.entry(x).or_insert(0) += 1;
        }
        ans
    }
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

【Java】6142. 统计坏数对的数目 91.71% 附类似等式交换问题

✇LeetCode 每日一题题解
wa-pian-d

解题思路

j - i != nums[j] - nums[i]
交换一下
j - nums[j] != i - nums[i]
就解了

把向前找的问题变成当前 + 哈希问题。避免了向前找的动作。

类似的

[中等] 1814. 统计一个数组中好对子的数目【数组】【哈希表】【数学】【计数】 [哈希表] [1814. 统计一个数组中好对子的数目]

代码

###java

class Solution {
public long countBadPairs(int[] nums) {
long ans = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int val = i - nums[i];
int same = map.getOrDefault(val, 0);
ans += i - same;
map.put(val, same + 1);
}
return ans;
}
}

每日一题-统计坏数对的数目🟡

✇LeetCode 每日一题题解

给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个 坏数对 。

请你返回 nums 中 坏数对 的总数目。

 

示例 1：

输入：nums = [4,1,3,3]
输出：5
解释：数对 (0, 1) 是坏数对，因为 1 - 0 != 1 - 4 。
数对 (0, 2) 是坏数对，因为 2 - 0 != 3 - 4, 2 != -1 。
数对 (0, 3) 是坏数对，因为 3 - 0 != 3 - 4, 3 != -1 。
数对 (1, 2) 是坏数对，因为 2 - 1 != 3 - 1, 1 != 2 。
数对 (2, 3) 是坏数对，因为 3 - 2 != 3 - 3, 1 != 0 。
总共有 5 个坏数对，所以我们返回 5 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：没有坏数对。

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

式子变形 + 枚举右维护左（Python/Java/C++/Go/JS/Rust）

✇LeetCode 每日一题题解
endlesscheng

前置题目：1512. 好数对的数目

题目要求

$$
j - i \ne \textit{nums}[j] - \textit{nums}[i]
$$

移项得

$$
\textit{nums}[i]-i \ne \textit{nums}[j]-j
$$

正难则反，用总数对个数 $\dfrac{n(n-1)}{2}$ 减去满足

$$
\textit{nums}[i]-i = \textit{nums}[j]-j
$$

的数对个数，即为答案。

设 $a[i] = \textit{nums}[i]-i$，就和 1512 题完全一样了。

为什么要先更新 $\textit{ans}$，再更新 $\textit{cnt}$？理由见 1512 题 我的题解。

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        ans = comb(len(nums), 2)
        cnt = defaultdict(int)
        for i, x in enumerate(nums):
            ans -= cnt[x - i]
            cnt[x - i] += 1
        return ans

class Solution {
    public long countBadPairs(int[] nums) {
        int n = nums.length;
        long ans = (long) n * (n - 1) / 2;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i] - i;
            int c = cnt.getOrDefault(x, 0);
            ans -= c;
            cnt.put(x, c + 1);
        }
        return ans;
    }
}

class Solution {
    public long countBadPairs(int[] nums) {
        int n = nums.length;
        long ans = (long) n * (n - 1) / 2;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < n; i++) {
            ans -= cnt.merge(nums[i] - i, 1, Integer::sum) - 1;
        }
        return ans;
    }
}

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        int n = nums.size();
        long long ans = 1LL * n * (n - 1) / 2;
        unordered_map<int, int> cnt;
        for (int i = 0; i < n; i++) {
            ans -= cnt[nums[i] - i]++;
        }
        return ans;
    }
};

func countBadPairs(nums []int) int64 {
    n := len(nums)
    ans := n * (n - 1) / 2
    cnt := map[int]int{}
    for i, x := range nums {
        ans -= cnt[x-i]
        cnt[x-i]++
    }
    return int64(ans)
}

var countBadPairs = function(nums) {
    const n = nums.length;
    let ans = n * (n - 1) / 2;
    const cnt = new Map();
    for (let i = 0; i < n; i++) {
        const x = nums[i] - i;
        const c = cnt.get(x) ?? 0;
        ans -= c;
        cnt.set(x, c + 1);
    }
    return ans;
};

use std::collections::HashMap;

impl Solution {
    pub fn count_bad_pairs(nums: Vec<i32>) -> i64 {
        let n = nums.len() as i64;
        let mut ans = n * (n - 1) / 2;
        let mut cnt = HashMap::new();
        for (i, x) in nums.into_iter().enumerate() {
            let e = cnt.entry(x - i as i32).or_insert(0);
            ans -= *e as i64;
            *e += 1;
        }
        ans
    }
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
  • 空间复杂度：$\mathcal{O}(n)$。

更多相似题目，见下面数据结构题单中的「§0.1 枚举右，维护左」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
  7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

Java36毫秒 计数+求和

✇LeetCode 每日一题题解
zhy-

解题思路

1.差值(数值-下标)相同的数可以组成好数对，按相同差值聚合计数。
2.设数组长度为n，数组总共数对个数为(n-1)+(n-2)+...+1累加之和，形成等差数列，公式求和(1+n-1)*(n-1)/2，得到总数对个数。相同差值的个数也可以视为数组长度，同理得到好数对个数。
3.坏数对=总数对-好数对。

统计坏数对的数目.png

代码

###java

class Solution {
    public long countBadPairs(int[] nums) {
        int n=nums.length;
        long cnt=(long)(1.0d*(1+n-1)*(n-1)/2);
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<n;i++){
            int d=nums[i]-i;
            map.put(d,map.getOrDefault(d,0)+1);
        }
        for(int count:map.values()){
            cnt-=(long)(1.0d*(1+count-1)*(count-1)/2);
        }
        return cnt;
    }
}

枚举

✇LeetCode 每日一题题解
tsreaper

解法：枚举

坏数对的数目，就是所有数对的数目，减去满足 i < j 且 j - i == nums[j] - nums[i] 的数对数目。

把等式两边移项，变为 nums[i] - i == nums[j] - j。因此我们只需要维护一个 unordered_map<int, int> mp，mp[x] 表示目前为止满足 nums[i] - i == x 的 i 有几个。我们枚举 j，并从答案中减去 mp[nums[j] - j] 的值即可。复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###c++

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        int n = nums.size();
        long long ans = 1LL * n * (n - 1) / 2;
        unordered_map<int, int> mp;
        for (int i = 0; i < n; i++) {
            int t = nums[i] - i;
            ans -= mp[t];
            mp[t]++;
        }
        return ans;
    }
};

[Python3/Java/C++/Go/TypeScript] 一题一解：枚举（清晰题解）

✇LeetCode 每日一题题解
lcbin

方法一：枚举

我们先在 $[0, n)$ 的范围内枚举下标 $j$，然后在 $[0, j)$ 的范围内枚举下标 $i$，统计满足 $\textit{nums}[i] = \textit{nums}[j]$ 且 $(i \times j) \bmod k = 0$ 的数对个数。

###python

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        ans = 0
        for j, y in enumerate(nums):
            for i, x in enumerate(nums[:j]):
                ans += int(x == y and i * j % k == 0)
        return ans

###java

class Solution {
    public int countPairs(int[] nums, int k) {
        int ans = 0;
        for (int j = 1; j < nums.length; ++j) {
            for (int i = 0; i < j; ++i) {
                ans += nums[i] == nums[j] && (i * j % k) == 0 ? 1 : 0;
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int ans = 0;
        for (int j = 1; j < nums.size(); ++j) {
            for (int i = 0; i < j; ++i) {
                ans += nums[i] == nums[j] && (i * j % k) == 0;
            }
        }
        return ans;
    }
};

###go

func countPairs(nums []int, k int) (ans int) {
for j, y := range nums {
for i, x := range nums[:j] {
if x == y && (i*j%k) == 0 {
ans++
}
}
}
return
}

###ts

function countPairs(nums: number[], k: number): number {
    let ans = 0;
    for (let j = 1; j < nums.length; ++j) {
        for (let i = 0; i < j; ++i) {
            if (nums[i] === nums[j] && (i * j) % k === 0) {
                ++ans;
            }
        }
    }
    return ans;
}

###rust

impl Solution {
    pub fn count_pairs(nums: Vec<i32>, k: i32) -> i32 {
        let mut ans = 0;
        for j in 1..nums.len() {
            for (i, &x) in nums[..j].iter().enumerate() {
                if x == nums[j] && (i * j) as i32 % k == 0 {
                    ans += 1;
                }
            }
        }
        ans
    }
}

###c

int countPairs(int* nums, int numsSize, int k) {
    int ans = 0;
    for (int j = 1; j < numsSize; ++j) {
        for (int i = 0; i < j; ++i) {
            ans += (nums[i] == nums[j] && (i * j % k) == 0);
        }
    }
    return ans;
}

时间复杂度 $O(n^2)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

每日一题-统计数组中相等且可以被整除的数对🟢

✇LeetCode 每日一题题解

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ，请你返回满足 0 <= i < j < n ，nums[i] == nums[j] 且 (i * j) 能被 k 整除的数对 (i, j) 的 数目 。

 

示例 1：

输入：nums = [3,1,2,2,2,1,3], k = 2
输出：4
解释：
总共有 4 对数符合所有要求：
- nums[0] == nums[6] 且 0 * 6 == 0 ，能被 2 整除。
- nums[2] == nums[3] 且 2 * 3 == 6 ，能被 2 整除。
- nums[2] == nums[4] 且 2 * 4 == 8 ，能被 2 整除。
- nums[3] == nums[4] 且 3 * 4 == 12 ，能被 2 整除。

示例 2：

输入：nums = [1,2,3,4], k = 1
输出：0
解释：由于数组中没有重复数值，所以没有数对 (i,j) 符合所有要求。

 

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i], k <= 100

双周赛t1 基于筛法的O(nlogn)解法

✇LeetCode 每日一题题解
981377660LMT

解题思路

类似于周赛t4 6015. 统计可以被 K 整除的下标对数目

  1. 筛法预处理每个因子的倍数有哪些，记录倍数时也要记录他对应的数组里的值
  2. 遍历每个数，分index=0与index>0的情况
  3. index=0直接特殊处理即可
  4. index>0时加上符合题意的配对数multiCounter[need][value],注意要减去自身重复取的情况，最后结果除以二即可

代码

###python3

from collections import defaultdict
from math import gcd
from typing import Counter, List

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        n = len(nums)
        multiCounter = defaultdict(lambda: defaultdict(int))
        for factor in range(1, n):
            for multi in range(factor, n, factor):
                multiCounter[factor][nums[multi]] += 1

        counter = Counter(nums)
        res1, res2 = 0, 0
        for index, value in enumerate(nums):
            if index == 0:
                res1 += counter[value] - 1
            else:
                need = k // gcd(index, k)
                res2 += multiCounter[need][value]
                if index ** 2 % k == 0:
                    res2 -= 1

        return res1 + res2 // 2

O(nlogn) 数学做法，枚举右维护左（Python/Java/C++/Go）

✇LeetCode 每日一题题解
endlesscheng

如果数组长度 $n=10^5$，$\mathcal{O}(n^2)$ 的暴力枚举就超时了，怎么优化？

从特殊到一般，先考虑所有 $\textit{nums}[i]$ 都相同的情况。此时问题简化成：

  • 统计 $0 \le i < j < n$ 且 $ij$ 能被 $k$ 整除的下标对 $(i, j)$ 的数目。

由于 $0$ 不是因子，单独统计（$i=0$ 时，$ij=0$，一定能被 $k$ 整除），所以下面讨论 $1 \le i < j < n$ 的情况。

如果 $k=12$，$j=9$，哪些 $i$ 是满足要求的？

$i$ 如果是 $12$ 的倍数，肯定可以满足要求，因为 $12$ 的倍数一定能被 $12$ 整除。还有其他的 $i$ 吗？

注意到 $j=9$ 是 $3$ 的倍数，而 $12=4\times 3$，那么 $i$ 只需要是 $4$ 的倍数，便可以满足 $ij$ 是 $k$ 的倍数，因为这种情况下 $ij=(4i')(3j')=12i'j'$ 一定是 $12$ 的倍数。

换句话说，由于 $j$ 和 $k$ 的最大公因子（GCD）是 $3$，所以 $i$ 只需要是 $\dfrac{12}{3}=4$ 的倍数就可以满足要求，即 $i=4,8,12,\cdots$ 都是满足要求的。

一般地，枚举 $j$，那么 $i$ 必须是 $k'=\dfrac{k}{\text{GCD}(k,j)}$ 的倍数。

回到本题，多了一个元素值必须相同的约束。

遍历数组，设当前元素 $x=\textit{nums}[j]$，我们需要知道左边值为 $x$ 且下标是 $k'$ 的倍数的数的个数。怎么维护？例如 $\textit{nums}[4]=\textit{nums}[6]=50$，对于 $i=4$，把 $50$ 以及 $4$ 的所有因子 $1,2,4$，组成三个二元组 $(50,1),(50,2),(50,4)$ 加到哈希表中（统计二元组的个数）；对于 $i=6$，把 $50$ 以及 $6$ 的所有因子 $1,2,3,6$，组成四个二元组 $(50,1),(50,2),(50,3),(50,6)$ 加到哈希表中。这样如果后面遍历到一个值为 $50$ 的数，且 $k'=2$，通过查询哈希表中的 $(50,2)$ 的个数，就能知道，左边有两个数，值为 $50$ 且下标是 $2$ 的倍数。

# 预处理每个数的因子
MX = 101
divisors = [[] for _ in range(MX)]
for i in range(1, MX):
    for j in range(i, MX, i):
        divisors[j].append(i)

class Solution:
    def countPairs(self, nums: list[int], k: int) -> int:
        ans = 0
        cnt = defaultdict(int)
        for j, x in enumerate(nums):  # 枚举 j，计算左边有多少个符合要求的 i
            if j and x == nums[0]:
                ans += 1  # 单独统计 i=0 的情况
            k2 = k // gcd(k, j)  # i 必须是 k2 的倍数
            ans += cnt[(x, k2)]
            for d in divisors[j]:  # j 是 d 的倍数
                cnt[(x, d)] += 1
        return ans

class Solution {
    private static final int MX = 101;
    private static final List<Integer>[] divisors = new ArrayList[MX];

    static {
        Arrays.setAll(divisors, i -> new ArrayList<>());
        // 预处理每个数的因子
        for (int i = 1; i < MX; i++) {
            for (int j = i; j < MX; j += i) {
                divisors[j].add(i);
            }
        }
    }

    public int countPairs(int[] nums, int k) {
        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int j = 0; j < nums.length; j++) { // 枚举 j，计算左边有多少个符合要求的 i
            int x = nums[j];
            if (j > 0 && x == nums[0]) {
                ans++; // 单独统计 i=0 的情况
            }
            int k2 = k / gcd(k, j); // i 必须是 k2 的倍数
            // 用位运算把二元组 (x, k2) 合并成一个整数
            ans += cnt.getOrDefault(k2 << 10 | x, 0);
            for (int d : divisors[j]) { // j 是 d 的倍数
                cnt.merge(d << 10 | x, 1, Integer::sum); // cnt[d<<10|x]++
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        while (a != 0) {
            int tmp = b % a;
            b = a;
            a = tmp;
        }
        return b;
    }
}

const int MX = 101;
vector<int> divisors[MX];

auto init = [] {
    for (int i = 1; i < MX; i++) {
        for (int j = i; j < MX; j += i) {
            divisors[j].push_back(i);
        }
    }
    return 0;
}();

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int ans = 0;
        unordered_map<int, int> cnt;
        for (int j = 0; j < nums.size(); j++) { // 枚举 j，计算左边有多少个符合要求的 i
            int x = nums[j];
            if (j && x == nums[0]) {
                ans++; // 单独统计 i=0 的情况
            }
            int k2 = k / gcd(k, j); // i 必须是 k2 的倍数
            ans += cnt[k2 << 10 | x]; // 用位运算把二元组 (x, k2) 合并成一个整数
            for (int d : divisors[j]) { // j 是 d 的倍数
                cnt[d << 10 | x]++;
            }
        }
        return ans;
    }
};

const mx = 101
var divisors [mx][]int

func init() {
    // 预处理每个数的因子
    for i := 1; i < mx; i++ {
        for j := i; j < mx; j += i {
            divisors[j] = append(divisors[j], i)
        }
    }
}

func countPairs(nums []int, k int) (ans int) {
    type pair struct{ v, d int }
    cnt := map[pair]int{}
    for j, x := range nums { // 枚举 j，计算左边有多少个符合要求的 i
        if j > 0 && x == nums[0] {
            ans++ // 单独统计 i=0 的情况
        }
        k2 := k / gcd(k, j)
        ans += cnt[pair{x, k2}] // 统计左边有多少个数，值为 x 且下标是 k2 的倍数
        for _, d := range divisors[j] { // j 是 d 的倍数
            cnt[pair{x, d}]++
        }
    }
    return
}

func gcd(a, b int) int { for a != 0 { a, b = b%a, a }; return b }

复杂度分析

由调和级数可得，预处理的时间是 $\mathcal{O}(M\log M)$，其中 $M=100$。

  • 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{nums}$ 的长度。每次计算 GCD 需要 $\mathcal{O}(\log \min(k,n))$ 的时间。遍历 $1$ 到 $n-1$ 的所有因子跟预处理是一样的，由调和级数可得，需要 $\mathcal{O}(n\log n)$ 的时间。
  • 空间复杂度：$\mathcal{O}(n\log n)$。

相似题目

2183. 统计可以被 K 整除的下标对数目

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
  7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

每日一题-统计好子数组的数目🟡

✇LeetCode 每日一题题解

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。

一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。

子数组 是原数组中一段连续 非空 的元素序列。

 

示例 1：

输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。

示例 2：

输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：总共有 4 个不同的好子数组：
- [3,1,4,3,2,2] 有 2 对。
- [3,1,4,3,2,2,4] 有 3 对。
- [1,4,3,2,2,4] 有 2 对。
- [4,3,2,2,4] 有 2 对。

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i], k <= 109

【普通人包看懂的简单代码】滑动窗口

✇LeetCode 每日一题题解
demouo

思路

  1. 下标[left,right]区间内如果满足条件了，那么总长度n-right个都满足条件
  2. 此时left++，以新的起点试图重新判断是否满足条件 再重复步骤1.
class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        long long res=0;
        int sum=0;//成对的总数
        unordered_map<int,int>cnt;
         for(int left=0,right=0;right<nums.size();right++){
             cnt[nums[right]]++;
            if(cnt[nums[right]]>=2){//可以成对就能为对的总数做贡献
              sum+=cnt[nums[right]]-1;//两个数多一对；三个数多两对；四个数多三对 
            }
            if(sum>=k){//对数不少于k
                while(sum>=k){
                res+=nums.size()-right;//right及其往后的都是好数组
                if(cnt[nums[left]]>=2){//滑出left时 如果left曾经对sum有过贡献 就得把它的贡献减掉
                    sum-=cnt[nums[left]]-1;
                }
                cnt[nums[left]]--;
                left++;//滑出left
                }
            }
         }
         return res;
    }
};

c++滑动窗口

✇LeetCode 每日一题题解
thdlrt
  • 思路
    • 直接枚举区间[i,j]会超时，可以使用滑动窗口来实现
    • 如果[i,j]是好子数组，那么[i,j+1],[i,j+2]...都是好子数组
    • 因此我们只需要枚举左边界i，找到最小的j使得[i,j]是好子数组，也就得到了nums.size()-j个以i开始的好子数组
    • 计算区间内相等元素对的数目：
      • 如果一个数字有k个(k>1)那么相等对有k*(k-1)/2个
      • 因此k加一时数对数目增加k*(k-1)/2-(k-1)*(k-2)/2=k-1个
      • 减少时同理
class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        long long ans=0;
        unordered_map<int,int>check;//维护滑动窗口内数据数目
        int sum=0;
        for(int i=0,j=0;j<nums.size();j++)
        {
            check[nums[j]]++;
            if(check[nums[j]]>1)//更新数对数目
                sum+=check[nums[j]]-1;
            if(sum>=k)
            {
                while(sum>=k)
                {
                    ans+=nums.size()-j;//更新i开始的好子数组数目
                    if(check[nums[i]]>1)
                        sum-=check[nums[i]]-1;
                    check[nums[i]]--;
                    i++;
                }
            }
        }
        return ans;
    }
};

「越长越合法」型滑动窗口（Python/Java/C++/Go/JS/Rust）

✇LeetCode 每日一题题解
endlesscheng

前置知识：滑动窗口【基础算法精讲 03】。

核心思路：

  1. 如果窗口中有 $c$ 个元素 $x$，再进来一个 $x$，会新增 $c$ 个相等数对。
  2. 如果窗口中有 $c$ 个元素 $x$，再去掉一个 $x$，会减少 $c-1$ 个相等数对。

用一个哈希表 $\textit{cnt}$ 维护子数组（窗口）中的每个元素的出现次数，以及相同数对的个数 $\textit{pairs}$。

外层循环：从小到大枚举子数组右端点 $\textit{right}$。现在准备把 $x=\textit{nums}[\textit{right}]$ 移入窗口，那么窗口中有 $\textit{cnt}[x]$ 个数和 $x$ 相同，所以 $\textit{pairs}$ 会增加 $\textit{cnt}[x]$。然后把 $\textit{cnt}[x]$ 加一。

内层循环：如果发现 $\textit{pairs}\ge k$，说明子数组符合要求，右移左端点 $\textit{left}$，先把 $\textit{cnt}[\textit{nums}[\textit{left}]]$ 减少一，然后把 $\textit{pairs}$ 减少 $\textit{cnt}[\textit{nums}[\textit{left}]]$。

内层循环结束后，$[\textit{left},\textit{right}]$ 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环，$[\textit{left}-1,\textit{right}]$ 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 $[\textit{left}-1,\textit{right}]$，还有 $[\textit{left}-2,\textit{right}],[\textit{left}-3,\textit{right}],\ldots,[0,\textit{right}]$ 都是满足要求的。也就是说，当右端点固定在 $\textit{right}$ 时，左端点在 $0,1,2,\ldots,\textit{left}-1$ 的所有子数组都是满足要求的，这一共有 $\textit{left}$ 个。

class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)  # 比 Counter() 快
        ans = left = pairs = 0
        for x in nums:
            pairs += cnt[x]
            cnt[x] += 1
            while pairs >= k:
                cnt[nums[left]] -= 1
                pairs -= cnt[nums[left]]
                left += 1
            ans += left
        return ans

class Solution {
    public long countGood(int[] nums, int k) {
        long ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        int pairs = 0;
        int left = 0;
        for (int x : nums) {
            int c = cnt.getOrDefault(x, 0);
            pairs += c; // 进
            cnt.put(x, c + 1);
            while (pairs >= k) {
                x = nums[left];
                c = cnt.get(x);
                pairs -= c - 1; // 出
                cnt.put(x, c - 1);
                left++;
            }
            ans += left;
        }
        return ans;
    }
}

class Solution {
    public long countGood(int[] nums, int k) {
        long ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        int pairs = 0;
        int left = 0;
        for (int x : nums) {
            pairs += cnt.merge(x, 1, Integer::sum) - 1; // pairs += cnt[x]++
            while (pairs >= k) {
                pairs -= cnt.merge(nums[left], -1, Integer::sum); // pairs -= --cnt[nums[left]]
                left++;
            }
            ans += left;
        }
        return ans;
    }
}

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        long long ans = 0;
        unordered_map<int, int> cnt;
        int pairs = 0, left = 0;
        for (int x : nums) {
            pairs += cnt[x]++;
            while (pairs >= k) {
                pairs -= --cnt[nums[left]];
                left++;
            }
            ans += left;
        }
        return ans;
    }
};

func countGood(nums []int, k int) (ans int64) {
    cnt := map[int]int{}
    pairs, left := 0, 0
    for _, x := range nums {
        pairs += cnt[x]
        cnt[x]++
        for pairs >= k {
            cnt[nums[left]]--
            pairs -= cnt[nums[left]]
            left++
        }
        ans += int64(left)
    }
    return
}

var countGood = function(nums, k) {
    const cnt = new Map();
    let ans = 0, pairs = 0, left = 0;
    for (const x of nums) {
        const c = cnt.get(x) ?? 0;
        pairs += c; // 进
        cnt.set(x, c + 1);
        while (pairs >= k) {
            const x = nums[left];
            const c = cnt.get(x);
            pairs -= c - 1; // 出
            cnt.set(x, c - 1);
            left++;
        }
        ans += left;
    }
    return ans;
};

use std::collections::HashMap;

impl Solution {
    pub fn count_good(nums: Vec<i32>, k: i32) -> i64 {
        let mut ans = 0;
        let mut cnt = HashMap::new();
        let mut pairs = 0;
        let mut left = 0;
        for &x in &nums {
            let e = cnt.entry(x).or_insert(0);
            pairs += *e;
            *e += 1;
            while pairs >= k {
                let e = cnt.get_mut(&nums[left]).unwrap();
                *e -= 1;
                pairs -= *e;
                left += 1;
            }
            ans += left;
        }
        ans as _
    }
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为 $\textit{nums}$ 的长度。虽然写了个二重循环，但是内层循环中对 $\textit{left}$ 加一的总执行次数不会超过 $n$ 次，所以总的时间复杂度为 $\mathcal{O}(n)$。
  • 空间复杂度：$\mathcal{O}(n)$。

更多相似题目，见下面滑动窗口题单中的「§2.3.1 越长越合法」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
  7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

每日一题-统计数组中好三元组数目🔴

✇LeetCode 每日一题题解

给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的 排列 。

好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。

请你返回好三元组的 总数目 。

 

示例 1：

输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3]
输出：1
解释：
总共有 4 个三元组 (x,y,z) 满足 pos1x < pos1y < pos1z ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。
这些三元组中，只有 (0,1,3) 满足 pos2x < pos2y < pos2z 。所以只有 1 个好三元组。

示例 2：

输入：nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
输出：4
解释：总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。

 

提示：

  • n == nums1.length == nums2.length
  • 3 <= n <= 105
  • 0 <= nums1[i], nums2[i] <= n - 1
  • nums1 和 nums2 是 [0, 1, ..., n - 1] 的排列。
❌