2748. 美丽下标对的数目

题目描述：

给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、 j 满足 0 ≤ i < j < nums.length ，如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质 ，则认为 nums[i] 和 nums[j] 是一组 美丽下标对 。

返回 nums 中 美丽下标对 的总数目。

对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质 。换而言之，如果 gcd(x, y) == 1 ，则认为 x 和 y 互质，其中 gcd(x, y) 是 x 和 y 的 最大公因数 。

示例 1：

输入：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

---

解题分析及思路：

方法：哈希表

思路：

本题可以采用暴力直接求解，依次比较每个元素。

先计算nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字，然后判断是否互质即可。

// nums[i] 的 第一个数字
var tempI = nums[i]
for tempI >= 10 {
    tempI = tempI / 10
}

// nums[j] 的 第一个数字
tempJ := nums[j] % 10

可以用gcd方法判断是否互质：

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

当然，个位数的质数也有限，可以直接用哈希表保存来判断

var m = map[int]map[int]bool{
	1: {
		1: true,
		2: true,
		3: true,
		4: true,
		5: true,
		6: true,
		7: true,
		8: true,
		9: true,
	},
	2: {
		1: true,
		3: true,
		5: true,
		7: true,
		9: true,
	},
	3: {
		1: true,
		2: true,
		4: true,
		5: true,
		7: true,
		8: true,
	},
	4: {
		1: true,
		3: true,
		5: true,
		7: true,
		9: true,
	},
	5: {
		1: true,
		2: true,
		3: true,
		4: true,
		6: true,
		7: true,
		8: true,
		9: true,
	},
	6: {
		1: true,
		5: true,
		7: true,
	},
	7: {
		1: true,
		2: true,
		3: true,
		4: true,
		5: true,
		6: true,
		8: true,
		9: true,
	},
	8: {
		1: true,
		3: true,
		5: true,
		7: true,
		9: true,
	},
	9: {
		1: true,
		2: true,
		4: true,
		5: true,
		7: true,
		8: true,
	},
}

func countBeautifulPairs(nums []int) (result int) {
	for i := 0; i < len(nums); i++ {
		var tempI = nums[i]
		for tempI >= 10 {
			tempI = tempI / 10
		}
		for j := i + 1; j < len(nums); j++ {
			tempJ := nums[j] % 10
			if _, ok := m[tempI][tempJ]; ok {
				result++
			}
		}
	}
	return
}

复杂度：

• 时间复杂度：O(N²)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:30 ms,击败了8.70% 的Go用户
• 内存消耗:4.2 MB,击败了100.00% 的Go用户