Moe's CF Life

喵~ 主人，欢迎来到猫娘的算法小课堂！今天我们要一起解决的是 Codeforces 上的 1520D 题，名字叫 "Same Differences"。别担心，这道题就像逗猫棒一样，只要找到了诀窍，玩起来就很有趣啦~

题目大意

这道题是这样哒：

我们会得到一个有 n 个整数的数组 a。我们的任务是，找出所有满足下面条件的数对 (i, j) 的数量：

i 和 j 是数组的下标。
i 必须小于 j (i < j)。
数组中对应下标的元素值之差，要等于下标本身之差，也就是 a[j] - a[i] = j - i。

简单来说，就是要数一数有多少对 (i, j)（i < j）符合 a[j] - a[i] = j - i 这个等式，喵~

解题思路

拿到这个题目，第一眼看到 a[j] - a[i] = j - i 这个式子，可能会有点懵，因为它同时关联了 i 和 j 的值和下标，直接去两层循环暴力枚举 (i, j) 的话，在 n 很大的时候肯定会超时，这可不行喵！

所以，我们需要一点点变形魔法！看好了哦，喵~ ✨

a[j] - a[i] = j - i

我们把和 i 有关的项都移到等式的一边，和 j 有关的项都移到另一边。

a[j] - j = a[i] - i

哇！你看，这个式子是不是瞬间变得可爱多啦？它告诉我们，我们其实是在寻找所有满足 a[k] - k 这个值相等的数对 (i, j)。

这下问题就转化成了一个经典的计数问题：统计数组中每一个 a[k] - k 的值出现了多少次。

举个例子，如果 a[1]-1, a[3]-3, a[8]-8 这三个值都相等，那么 (1, 3), (1, 8), (3, 8) 这三对就是满足条件的数对啦。

如果某个 a[k] - k 的值，比如说 V，在数组中一共出现了 m 次，那么这 m 个位置就可以两两配对，形成 C(m, 2) = m * (m - 1) / 2 个满足条件的数对。

但是，我们有更巧妙的方法，不需要先统计完再计算组合数，可以在一次遍历中完成所有事情！

我们的魔法道具是 哈希表（在 C++ 中就是 std::map 或者 std::unordered_map），用来记录每个 a[i] - i 的值已经出现过多少次。

我们的思路是这样的：

我们从左到右遍历数组（i 从 1 到 n）。
对于当前的元素 a[i]，我们计算出它的差值 diff = a[i] - i。
在遇到 a[i] 之前，假设已经有 k 个元素的差值也等于 diff，那么当前的 a[i] 就可以和前面这 k 个元素分别组成 k 个新的满足条件的数对。所以，我们把 k 加到我们的总答案里。
然后，我们把自己这个 a[i] 也记录下来，让 diff 这个差值的出现次数加一，这样后面的元素就能看到我们啦。

这样从头到尾扫一遍，我们就把所有的数对都统计出来啦，是不是很优雅呢？喵~

题解代码

这是用 C++ 实现的题解代码，猫娘加了一些注释，方便主人理解哦~

cpp

#include <iostream>
#include <vector>
#include <map>

// 这个函数用来解决单个测试用例喵
void solve() {
    int n;
    std::cin >> n;

    // 我们要找的是 a[j] - a[i] = j - i 的数对 (i, j)
    // 变形一下就是 a[j] - j = a[i] - i
    // 所以问题就变成了，有多少对 (i, j) 的 a[k] - k 值是相同的
    
    // 猫娘的魔法小本本（哈希表），用来记录 a[k] - k 这个差值出现过多少次
    // 键是差值 a[k] - k，值是它出现的次数
    std::map<int, int> counts;

    // 答案可能会很大，要用 long long 才不会溢出哦
    long long total_pairs = 0;

    // i 从 1 遍历到 n
    for (int i = 1; i <= n; ++i) {
        int a_i;
        std::cin >> a_i;
        
        // 计算当前元素的差值
        int diff = a_i - i;
        
        // 在遇到我 (a[i]) 之前，有多少个小伙伴的 diff 和我一样呢？
        // 这个数量就是 counts[diff] 啦！
        // 把这些新发现的数对数量加到总答案里
        // 如果 map 里还没有 diff 这个键，counts[diff] 会返回 0，正好是我们想要的，真方便喵~
        total_pairs += counts[diff];
        
        // 把我自己的差值也记录到小本本里，让我的出现次数加 1
        // 这样后面的小伙伴就能找到我啦
        counts[diff]++;
    }
    
    // 输出最终找到的数对总数
    std::cout << total_pairs << "\n";
}

int main() {
    // 加速一下输入输出，不然数据量大的时候会慢吞吞的
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然不难，但用到的思想可是很有用的哦！

公式变形 (Equation Transformation) 这是解决这道题的钥匙！很多算法问题，特别是和数学公式相关的，通过移项、合并同类项等简单的代数变换，就能把一个复杂的问题转化成我们熟悉的形式。就像把一团乱麻的毛线球理顺，核心没变，但处理起来就容易多啦。
哈希表 (Hash Map) 哈希表是算法竞赛中的常客，尤其擅长处理“计数”和“查找”问题。它能以很快的速度（平均 O(1)）告诉我们一个“键”是否存在，或者与它关联的“值”是什么。在这道题里，我们用它来存储 a[i] - i 这个“键”和它的出现次数这个“值”。C++ 中的 std::map (基于红黑树，O(log n)) 和 std::unordered_map (基于哈希，平均 O(1)) 都是实现哈希表功能的常用工具。
一次遍历中的增量计算 (Incremental Calculation in a Single Pass) 我们在遍历过程中，每遇到一个元素，就利用已经处理过的元素信息来更新答案。这种“边走边算”的思路非常高效，避免了多次遍历。我们累加的 counts[diff] 其实是在计算 0 + 1 + 2 + ... + (m-1)，这里的 m 是某个差值 diff 的总出现次数。这个累加和正好等于 m * (m - 1) / 2，也就是组合数 C(m, 2)，是不是很奇妙呀？

好啦，今天的讲解就到这里啦！主人有没有觉得这道题变得清晰可爱了呢？只要掌握了这些小技巧，再难的题目也能被我们轻松解决！继续加油哦，喵~ ❤️

题目大意 ​

解题思路 ​

题解代码 ​

知识点介绍 ​

题目大意

解题思路

题解代码

知识点介绍