输入：nums = [2,5,1,4]
输出：5
解释：nums 中共有 5 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 5 。2 和 5 互质，因此 gcd(2,5) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 2 ，nums[2] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(2,1) == 1 。
i = 1 和 j = 2 ：nums[1] 的第一个数字是 5 ，nums[2] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(5,1) == 1 。
i = 1 和 j = 3 ：nums[1] 的第一个数字是 5 ，nums[3] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(5,4) == 1 。
i = 2 和 j = 3 ：nums[2] 的第一个数字是 1 ，nums[3] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(1,4) == 1 。
因此，返回 5 。

示例 2：

输入：nums = [11,21,12]
输出：2
解释：共有 2 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 1 。gcd(1,1) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 1 ，nums[2] 的最后一个数字是 2 。gcd(1,2) == 1 。
因此，返回 2 。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 9999
nums[i] % 10 != 0

前提欧几里得算法

欧几里得算法是一种用于计算两个整数的最大公约数（GCD, Greatest Common Divisor）的高效方法。这个算法基于两个基本原理：

如果一个数是另一个数的约数，那么最大公约数就是较小的那个数。
两个数的最大公约数等于其中较小的那个数和两数之差的最大公约数。

具体来说，欧几里得算法利用了以下性质：

对于两个整数 a 和 b （假设 $a \ge b$ ），它们的最大公约数 $\text{gcd}(a, b)$ 等于 $\text{gcd}(b, a % b)$
这个性质的证明如下：

设 a 和 b 的最大公约数为 d ，即 d 整除 a 和 b 。即 $ a % d = b
% d = 0 $

根据除法原理，我们可以写出 a 和 b 的除法关系：
$ a = b \cdot q + r $
其中 q 是商， r 是余数，满足 $0 \le r < b$ 。

因为 d 是 a 和 b 的公约数，所以 d 也必须整除 a 和 b 的线性组合 $ a - b \cdot q = r $ 即： $ (a - b \cdot q) % d = 0 $ 因此， d 也整除 r 。

所以， a 和 b 的最大公约数等于 b 和 r 的最大公约数，即 $\text{gcd}(a, b) = \text{gcd}(b, r) $。

基于这个性质，我们可以不断用较小数的余数替代较大数，直到较小数变为 0。此时较大数就是两个数的最大公约数。

算法步骤

初始化两个数 a 和 b 。
计算 a % b 得到余数 r 。
将 a 赋值为 b ，将 b 赋值为 r 。
重复步骤 2 和 3，直到 b 变为 0。
此时 a 即为 a 和 b 的最大公约数。

分析

枚举全部符合下标关系：0 <= i < j < n的元素对
求nums[i]的第一个数字，求nums[j]的最后一个数字
判断是否互质，互质则计数器+1

枚举+互质判断

互质算法
对于整数a,b
- 如果b == 0，则最大公约数为a
  - 否则：a和b的最大公约数等价于 b, a % b的最大公约数

class Solution {
    public int countBeautifulPairs(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int i = 0;i < n;i++) {
            for (int j = i + 1;j < n;j++) {
                int a = getFirst(nums[i]);
                int b = nums[j] % 10;
                if (gcd(a,b) == 1) {
                    count++;
                }
            }
        }
        return count;
    }

    // 互质算法
    private int gcd(int a,int b) {
        return b == 0 ? a: gcd(b,a % b); 
    }

    private int getFirst(int a) {
        while (a >= 10) {
            a = a / 10;
        }
        return a;
    }
}

哈希表高效枚举

只存储1-9的数字。

从下标小的开始枚举
初始化[1,9]哈希表
遍历 j in 1-9
- j 作为最高位之前出现过，判断是否互质
  - 互质，则结果递增
- 更新高位出现次数
返回结果

class Solution {
    public int countBeautifulPairs(int[] nums) {
        int ans = 0;
        int[] cnt = new int[10];
        for (int x : nums) {
            for (int y = 1; y < 10; y++) {
                // y之前出现过，作为num[i] x作为 nums[j]
                if (cnt[y] > 0 && gcd(y, x % 10) == 1) {
                    ans += cnt[y];
                }
            }
            while (x >= 10) {
                x /= 10;
            }
            cnt[x]++; // 统计最高位的出现次数
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com

2748、美丽下标对的数目

示例 1：

示例 2：

前提 欧几里得算法

算法步骤

分析

枚举+互质判断

哈希表 高效枚举

前提欧几里得算法

哈希表高效枚举