题目

题目"连连看"对角线遍历原理动画演示

可以摧毁的能量阵

解题思路

问题转化：求和 ≥ k 的连续子数组个数

题目要求统计所有连续子数组中，元素和 大于等于 k 的个数。
由于 n 最大为 1e5，不能使用 O(n^2) 的暴力枚举，必须优化。

核心性质：数组元素全为正

关键突破口：所有 a[i] ≥ 1，即数组元素严格为正。
这意味着：固定左端点后，区间和随右端点右移单调递增。
这一性质使得我们可以使用 二分查找 或 双指针（滑动窗口） 优化。

方法一：固定左端点 + 二分查找最小合法右端点

• 预处理前缀和，实现 O(1) 区间和查询。
• 对每个左端点 l，二分查找最小的 r 使得 [l, r] 和 ≥ k。
• 一旦找到，[l, r], [l, r+1], ..., [l, n] 共 n - r + 1 个区间都合法。

时间复杂度：O(nlogn)，适用于 n ≤ 1e5。

方法二：变长滑动窗口（双指针），利用单调性避免重复计算

由于数组全正，当右指针 r 右移时，当前窗口和增大；

利用“正数数组”的单调性，使用同向双指针维护一个动态窗口：

• 枚举右端点 r，将 nums[r] 加入窗口。

• 当当前窗口和 sum ≥ k 时：

  • 说明以当前 l 为左端点、r 到 n 为右端点的所有区间都合法。
  • 累加 n - r + 1 到答案。
  • 尝试收缩左边界（l++），直到窗口和 < k。

关键理解：一旦 [l, r] 满足条件，那么 [l, r+1], [l, r+2], ..., [l, n] 也一定满足（因为加的是正数）。

这种写法只需一次遍历，时间复杂度为 O(n)，更优。

为什么双指针能工作？

因为元素为正，左指针一旦右移，就不会再左移，每个元素最多进出窗口一次，保证线性复杂度。

参考代码

二分做法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        // 构建前缀和数组, prefix[i] 表示前 i 个数的和
        long[] prefix = new long[n + 5];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + sc.nextInt();
        }

        long cnt = 0;
        // 枚举左端点 l
        for (int l = 1; l <= n; l++) {
            // 二分查找最小的 r, 使得 [l, r] 的和 >= k
            int r = getR(l, n, k, prefix);
            if (r == -1) {
                // 从 l 开始的所有区间和都 < k, 后续 l 更大, 直接 break
                break;
            }
            // 所有 [l, r], [l, r+1], ..., [l, n] 都合法
            cnt += n - r + 1;
        }
        System.out.println(cnt);
    }

    // 返回最小的 r (>= start), 使得 prefix[r] - prefix[start-1] >= k
    // 若不存在, 返回 -1
    private static int getR(int start, int end, long k, long[] prefix) {
        int l = start, r = end;
        int result = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            long sum = prefix[mid] - prefix[start - 1];
            if (sum >= k) {
                result = mid;      // 记录候选答案
                r = mid - 1;       // 尝试找更小的 r
            } else {
                l = mid + 1;       // 和不够, 需要更大的 r
            }
        }
        return result;
    }
}

滑动窗口(双指针)解法（推荐）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        int[] nums = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextInt();
        }

        long sum = 0;   // 当前窗口 [l, r] 的和
        long cnt = 0;   // 合法方案总数

        // 双指针模板：枚举右边界 r
        for (int l = 1, r = 1; r <= n; r++) {
            // 将右边界 r 加入窗口
            sum += nums[r];

            // 当窗口和满足条件时, 收集答案并收缩左边界
            while (l <= r && sum >= k) {
                // 此时 [l, r], [l, r+1], ..., [l, n] 共 (n - r + 1) 个区间都合法
                cnt += n - r + 1;
                // 移除左边界 l, 尝试更小的窗口
                sum -= nums[l];
                l++;
            }
        }

        System.out.println(cnt);
    }
}

代码模板

我使用的变长滑动窗口模板总结

for (右指针 r 从 1 到 n) {
    将 r 加入窗口；
    while (窗口满足条件) {
        收集以当前 l 为左端点的所有合法答案；
        移除 l，l++；
    }
}

计算方程

解题思路

核心观察：函数单调性

题目要求找到最小的正整数 x，使得： sqrt(x) + floor(log_k(x)) - m > 0

分析函数性质：

• sqrt(x) 随 x 增大而增大（严格递增）
• floor(log_k(x)) 是非递减的（当 x 跨越 k^p 时才增加）
• 两者之和整体是严格单调递增的

也可以通过求导证明函数递增性质。

因此，一旦某个 x 满足条件，所有更大的 x 也都满足。
这说明答案具有二段性，可以使用二分查找。

二分策略：找第一个满足条件的 x

我们二分搜索最小的 x，使得表达式值 > 0。
搜索范围：

• 左边界：1（正整数）
• 右边界：可设为较大值（如 1e18），但实际答案远小于此

对每个 mid，计算： value = sqrt(mid) + floor(log_k(mid)) - m

若 value > 0，说明 mid 可能是答案，尝试更小的值（r = mid - 1）；
否则，说明 mid 太小，需增大（l = mid + 1）。

注意：浮点精度问题

使用 Math.log(x) / Math.log(k) 计算对数时，浮点误差可能导致 floor 结果错误。
例如：当 x = k^p 时，理论上 log_k(x) = p，但浮点计算可能得到 p - 1e-15，floor 后变成 p - 1。

解决方案：手动实现整数对数向下取整（即 logFloor 函数）：

• 不断用 x /= k，直到 x < k
• 计数除法次数，即为 floor(log_k(x))

这样完全避免浮点运算，保证正确性。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long k = sc.nextLong();
            long m = sc.nextLong();

            // 二分查找最小的 x，使得 sqrt(x) + floor(log_k(x)) - m > 0
            long l = 1;
            long r = (long) 1e18;  // 足够大的上界
            long result = -1;

            while (l <= r) {
                long mid = l + (r - l) / 2;
                // double res = Math.sqrt(mid) + Math.floor(Math.log(mid) / Math.log(k)) - m;
                // 使用手动实现的整数对数，避免浮点误差
                long logVal = logFloor(mid, k);
                double sqrtVal = Math.sqrt(mid);
                double value = sqrtVal + logVal - m;

                if (value > 0) {
                    result = mid;
                    r = mid - 1;  // 尝试更小的 x
                } else {
                    l = mid + 1;  // x 太小，需要增大
                }
            }

            System.out.println(result);
        }
        sc.close();
    }

    // 手动计算 floor(log_base(x))
    private static long logFloor(long x, long base) {
        long res = 0;
        while (x >= base) {
            x /= base;
            res++;
        }
        return res;
    }
}

神奇的数组

解题思路

核心性质：异或 = 无进位加法

异或运算的本质是不进位的二进制加法。
因此，对于一组非负整数，它们的和等于异或值，当且仅当任意两个数在同一个二进制位上不会同时为 1。

换句话说：

整个区间内，每个比特位最多只能被一个数置为 1。
一旦有两个数在某一位都是 1，相加时就会产生进位，导致 sum > xor。

这个性质具有单调性：

• 如果区间 [l, r] 满足条件，那么它的任意子区间（如 [l, r-1]）也一定满足。
• 如果 [l, r] 不满足，那么 [l, r+1] 也一定不满足。

因此，对每个左端点 l，存在一个最大的右端点 R，使得 [l, R] 合法，而 [l, R+1] 非法。

二分做法：利用前缀和与前缀异或

• 预处理两个数组：
  • prefixSum[i]：前 i 个数的和
  • prefixXor[i]：前 i 个数的异或
• 区间 [l, r] 的和 = prefixSum[r] - prefixSum[l-1]
• 区间 [l, r] 的异或 = prefixXor[r] ^ prefixXor[l-1]
• 对每个 l，二分查找最大的 r 使得两者相等
• 合法子数组数量为 r - l + 1

时间复杂度：O(nlogn)

双指针做法：滑动窗口更高效

利用“一旦不合法，扩展右端只会更不合法”的特性，使用双指针维护一个最大合法窗口：

• 枚举右端点 r，将 nums[r] 加入窗口（更新 sum 和 xor）
• 若当前窗口 [l, r] 不满足 sum == xor，则不断右移 l 直到合法（或窗口为空）
• 此时，以 r 为右端点的所有合法子数组为 [l, r], [l+1, r], ..., [r, r]，共 r - l + 1 个

由于每个元素最多进出窗口一次，时间复杂度为 O(n)，且常数小，推荐使用。

参考代码

二分做法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 前缀和与前缀异或数组，下标从 1 开始
        long[] prefixSum = new long[n + 5];
        long[] prefixXor = new long[n + 5];
    
        for (int i = 1; i <= n; i++) {
            int num = sc.nextInt();
            prefixSum[i] = prefixSum[i - 1] + num;
            prefixXor[i] = prefixXor[i - 1] ^ num;
        }
    
        long result = 0;
        // 枚举左端点 l
        for (int l = 1; l <= n; l++) {
            // 二分查找最大的 r，使得 [l, r] 满足 sum == xor
            int r = getR(l, n, prefixSum, prefixXor);
            if (r != -1) {
                result += r - l + 1;
            }
        }
    
        System.out.println(result);
        sc.close();
    }

    // 返回最大的 r (>= start)，使得 [start, r] 满足 sum == xor
    // 若 [start, start] 就不满足，返回 -1
    private static int getR(int start, int end, long[] prefixSum, long[] prefixXor) {
        int l = start, r = end;
        int result = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            long sum = prefixSum[mid] - prefixSum[start - 1];
            long xor = prefixXor[mid] ^ prefixXor[start - 1];
        
            if (sum == xor) {
                result = mid;   // 记录合法位置
                l = mid + 1;    // 尝试更大的 r
            } else {
                r = mid - 1;    // 当前 mid 不合法，需缩小 r
            }
        }
        return result;
    }
}

双指针做法（推荐）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextInt();
        }
    
        long result = 0;
        long sum = 0;   // 当前窗口 [l, r] 的和
        long xor = 0;   // 当前窗口 [l, r] 的异或
    
        // 双指针模板：枚举右边界 r
        for (int l = 1, r = 1; r <= n; r++) {
            // 将右边界 r 加入窗口
            sum += nums[r];
            xor ^= nums[r];
        
            // 若当前窗口不合法，收缩左边界直到合法
            while (l <= r && sum != xor) {
                sum -= nums[l];
                xor ^= nums[l];  // 异或两次等于抵消
                l++;
            }
        
            // 此时 [l, r], [l+1, r], ..., [r, r] 全部合法
            result += r - l + 1;
        }
    
        System.out.println(result);
        sc.close();
    }
}

电池分组

解题思路

关键性质：异或的自反性与整体关系

设全部 n 个电池的总异或和为 totalXor = A1 XOR A2 XOR ... XOR An。

若能将数组划分为两个非空子集 S1 和 S2，使得：
xor(S1) == xor(S2)

那么对两边同时异或 xor(S1)，可得：
xor(S1) XOR xor(S2) == 0

而左边正是整个数组的异或和（因为 S1 ∪ S2 是全集，且不相交），即：

totalXor == 0

结论：

存在合法划分 当且仅当 所有元素的总异或和为 0。

为什么总异或为 0 就一定有解？

• 若 totalXor == 0，则任意一个非空前缀的异或值 x，其对应后缀的异或值也为 x（因为 x XOR x = 0）。

• 只要 n ≥ 2 （题目保证），我们总可以取第一个元素作为 S1 ，其余作为 S2 此时：

  • xor(S1) = A1
  • xor(S2) = totalXor XOR A1 = 0 XOR A1 = A1
  • 两者相等，且两组均非空。

因此，无需枚举分割点，只需判断总异或是否为 0。

✅ 直接计算总异或，若为 0 则 YES，否则 NO。

时间复杂度：每个测试用例 O(n)，最优解。

参考代码

最优解法（推荐）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int totalXor = 0;
            // 读入所有数并计算总异或
            for (int i = 0; i < n; i++) {
                totalXor ^= sc.nextInt();
            }
            // 总异或为 0 即可分成两个异或相等的非空组
            if (totalXor == 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

枚举分割点写法（正确但冗余）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int[] prefixXor = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                prefixXor[i] = prefixXor[i - 1] ^ sc.nextInt();
            }
        
            boolean found = false;
            // 枚举分割点 l（前 l 个为一组，剩下为另一组）
            // 注意：两组都必须非空，所以 l ∈ [1, n-1]
            for (int l = 1; l < n; l++) {
                int left = prefixXor[l];
                int right = prefixXor[n] ^ prefixXor[l];
                if (left == right) {
                    found = true;
                    break;
                }
            }
        
            System.out.println(found ? "YES" : "NO");
        }
    }
}

💡 提示：虽然枚举写法逻辑正确，但本质上它在验证 prefixXor[n] == 0。
因为 left == right ⇨ left == totalXor ^ left ⇨ totalXor == 0。
所以直接判断总异或更简洁高效。

可结合的元素对

解题思路

关键性质：lowbit(x) = x 当且仅当 x 是 2 的幂

题目条件 lowbit(a[i] + a[j]) == a[i] + a[j] 等价于：

a[i] + a[j] 是 2 的整数次幂（即 1, 2, 4, 8, 16, ...）。

因为 lowbit(x) 返回的是 x 二进制中最右边的 1 所代表的值，只有当 x 本身只有一个 1（即形如 2^k）时，才有 lowbit(x) == x。

所以问题转化为：统计有多少对 (i, j)（i < j），使得 a[i] + a[j] 是 2 的幂。

枚举目标和 + 哈希表优化

由于 a[i] ≤ 1e9，两个数之和最大约为 2e9，而 2^30 ≈ 1e9，2^31 ≈ 2e9，所以只需枚举 k = 0 到 30（或 31）即可覆盖所有可能的 2 的幂。

对每个右端点 j（从左到右遍历）：

• 枚举所有可能的 sum = 2^k
• 计算需要的 a[i] = sum - a[j]
• 查询前面已经出现过多少个这样的 a[i]（用哈希表 cnt 维护）

这样每对 (i, j) 只会被统计一次（i < j），且时间复杂度为 O(n * 31)，完全可行。

二分做法：排序 + 双重枚举

如果不使用哈希表，也可以先将数组排序，然后对每个 j：

• 在 [1, j-1] 范围内二分查找值等于 2^k - a[j] 的元素个数
• 使用 lowerBound 找第一个 ≥ target 的位置，再找第一个 ≥ target+1 的位置，两者之差即为出现次数

时间复杂度 O(n log n + n * 31 * log n)，比哈希表慢，但也能通过。

为什么哈希表更优？

• 哈希表做法是 O(31n)，常数小，代码简洁。
• 二分做法需要排序，且每次查询要 log n，适合不能用哈希或值域极大的场景，但本题哈希更直接。

参考代码

方法一：哈希表（推荐）

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextInt();
        }
    
        Map<Integer, Integer> cnt = new HashMap<>(); // 记录前面每个数值出现的次数
        long result = 0;
    
        // 枚举右端点 r
        for (int r = 1; r <= n; r++) {
            // 枚举所有可能的 2^k（k 从 0 到 31 足够覆盖 2e9）
            for (int k = 0; k <= 31; k++) {
                int targetSum = 1 << k;          // 2^k
                int needed = targetSum - nums[r]; // 需要的左端点值 a[i]
                // 如果 needed 为负数，跳过（因为 a[i] ≥ 1）
                if (needed < 0) continue;
                result += cnt.getOrDefault(needed, 0);
            }
            // 将当前 nums[r] 加入哈希表，供后续使用
            cnt.put(nums[r], cnt.getOrDefault(nums[r], 0) + 1);
        }
    
        System.out.println(result);
    }
}

方法二：排序 + 二分

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextInt();
        }
    
        // 对数组排序，便于二分查找
        Arrays.sort(nums, 1, n + 1);
        long result = 0;
    
        // 枚举右端点 r
        for (int r = 1; r <= n; r++) {
            // 枚举所有可能的 2^k
            for (int k = 0; k <= 30; k++) {
                int targetSum = 1 << k;
                int needed = targetSum - nums[r];
                if (needed < 0) continue;
                // 在 [1, r-1] 范围内统计值等于 needed 的元素个数
                int leftPos = lowerBound(nums, 1, r - 1, needed);
                int rightPos = lowerBound(nums, 1, r - 1, needed + 1);
                result += rightPos - leftPos;
            }
        }
    
        System.out.println(result);
    }

    // 在 nums[l..r] 中查找第一个 >= target 的位置
    static int lowerBound(int[] nums, int l, int r, int target) {
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) {
                r = mid - 1; // 尝试找更靠左的满足位置
            } else {
                l = mid + 1;
            }
        }
        return l; // l 是第一个 >= target 的下标
    }
}

等腰三角形

解题思路

问题转化：配对条件明确

每个三角形由 2 根相同长度的红色木棍（腰） + 1 根蓝色木棍（底） 构成。

根据三角形不等式，等腰三角形成立的充要条件是：

2 × 红色长度 > 蓝色长度

因为两腰相等，只需保证“两腰之和大于底边”，即 A[i] + A[i] > B[j]。

注意：每根红色木棍在序列 A 中只出现一次，但代表 2 根，所以每个 A[i] 最多用于 1 个三角形。
蓝色木棍每个 B[j] 只有 1 根，也只能用一次。

因此，问题转化为：从 A 和 B 中各选若干元素配对，使得 A[i] × 2 > B[j]，且每对 (i, j) 唯一，求最大配对数。

贪心策略：短红配短蓝，长红留着配长蓝

关键观察：

• 如果某个红色木棍能和某蓝色木棍配对（即 2*A[i] > B[j]），那么它也能和所有更短的蓝色木棍配对。
• 同理，如果某个蓝色木棍能和某红色木棍配对，那么它也能和所有更长的红色木棍配对。

为了最大化配对数量，应：

优先用较短的红色木棍去匹配尽可能短的、但仍能配对的蓝色木棍，把较长的红色木棍留给更难匹配的长蓝色木棍。

这正是典型的双指针贪心匹配模型。

排序 + 双指针实现

• 将 A（红）和 B（蓝）都从小到大排序。
• 使用两个指针：
  • a 遍历红色木棍（从短到长）
  • b 遍历蓝色木棍（从短到长）
• 对每个红色木棍 A[a]，尝试匹配当前最短的未匹配蓝色木棍 B[b]：
  • 如果 2 * A[a] > B[b]，说明可以配对，b++，答案加 1。
  • 否则，这个红色太短，跳过（因为后面蓝色更长，更配不上）。

这样能保证每个红色木棍都尝试匹配“当前最容易满足”的蓝色木棍，从而最大化总数。

参考代码

方法一：给蓝色木棍找合适的红色腰（推荐）

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] A = new int[n + 5]; // 红色木棍长度（每个代表2根）
        int[] B = new int[n + 5]; // 蓝色木棍长度（每个1根）

        for (int i = 1; i <= n; i++) {
            A[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            B[i] = sc.nextInt();
        }

        // 从小到大排序, 便于贪心匹配
        Arrays.sort(A, 1, n + 1);
        Arrays.sort(B, 1, n + 1);

        long result = 0;
        int b = 1; // 指向当前待匹配的最短蓝色木棍

        // 遍历每个红色木棍（按长度从小到大）
        for (int a = 1; a <= n; a++) {
            // 如果当前红色能和当前蓝色组成三角形
            if (2L * A[a] > B[b]) {
                result++; // 成功配对
                b++;      // 蓝色木棍被使用, 指向下一个
                if (b > n) break; // 所有蓝色已匹配完
            }
            // 如果不能配对, 说明 A[a] 太短, 直接跳过（后续蓝色更长, 更配不上）
        }

        System.out.println(result);
    }
}

方法二：从后往前匹配（等价写法）

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] A = new int[n + 5];
        int[] B = new int[n + 5];

        for (int i = 1; i <= n; i++) {
            A[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            B[i] = sc.nextInt();
        }

        Arrays.sort(A, 1, n + 1);
        Arrays.sort(B, 1, n + 1);

        long result = 0;
        int a = n; // 从最长的红色开始

        // 从最长的蓝色往短遍历
        for (int b = n; b >= 1 && a >= 1; b--) {
            // 如果当前最长的红色能和当前蓝色配对
            if (2L * A[a] > B[b]) {
                result++;
                a--; // 使用掉这个红色
            }
            // 如果不能配对, 说明这个蓝色太长, 无法和任何红色配对, 直接跳过
        }

        System.out.println(result);
    }
}

连连看

解题思路

核心观察：满足条件的点对必在同一条斜线上

题目要求两个格子 (a,b) 和 (c,d) 满足 |a−c| == |b−d| > 0 且值相等。这等价于：两点位于同一条 45° 或 135° 的对角线 上（即斜线），且不是同一个点。

关键性质：用坐标和/差唯一标识对角线

• 所有 / 方向（右上到左下）的点满足：x + y = 常数
• 所有 \ 方向（左上到右下）的点满足：y - x = 常数（或 x - y，符号不影响分组）
  → 我们可以按这两个“线号”分别处理每条对角线。

优化策略：用计数数组动态累积配对数，无需预存整条线

我们不需要先把一条对角线上所有数字存下来再算组合数。
关键洞察是：每遇到一个新值，它能和这条线上之前出现过的每一个相同值各组成一对。

举个例子：某条对角线上值依次是 2, 2, 2。

• 第一个 2：前面没有 2，新增 0 对
• 第二个 2：前面有 1 个 2，新增 1 对
• 第三个 2：前面有 2 个 2，新增 2 对
  总共 0 + 1 + 2 = 3 对，正好等于组合数 C(3,2)。

因此，我们只需一个计数数组 cnt（相当于轻量级哈希表），在遍历对角线时：

• 先读取 cnt[value]，先看之前出现过多少次当前值，这就是当前值能新增的无序对数量；
• 然后执行 cnt[value]++，为后续相同值做准备。

这样一遍扫描、O(1) 空间（每条线独立） 就完成了统计，既省空间又高效。

注意有序对要求

题目将 (A,B) 和 (B,A) 视为两个不同对，因此最终结果要 乘以 2。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] matrix = new int[n + 5][m + 5];
        // 读入数据，使用 1-indexed 避免边界问题
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        long result = 0;

        // 处理 / 方向对角线: x + y = line
        // 最小 line = 1+1 = 2, 最大 line = n + m
        for (int line = 2; line <= n + m; line++) {
            int[] cnt = new int[1005]; // 值域 <= 1000, 开 1005 足够
            for (int x = 1; x <= n; x++) {
                int y = line - x;
                // 检查 y 是否在有效列范围内 [1, m]
                if (y < 1 || y > m) {
                    continue;
                }
                // 先累加之前出现的相同值数量（新增无序对）
                result += cnt[matrix[x][y]];
                // 再更新计数
                cnt[matrix[x][y]]++;
            }
        }

        // 处理 \ 方向对角线: y - x = line
        // y - x 最小为 1 - n (y=1, x=n), 最大为 m - 1 (y=m, x=1)
        for (int line = m - 1; line >= 1 - n; line--) {
            int[] cnt = new int[1005];
            for (int x = 1; x <= n; x++) {
                int y = line + x; // 由 y - x = line 推出 y = line + x
                if (y < 1 || y > m) {
                    continue;
                }
                result += cnt[matrix[x][y]];
                cnt[matrix[x][y]]++;
            }
        }

        // 题目要求有序对，所以无序对总数乘以 2
        result *= 2;
        System.out.println(result);
    }
}