2748. 美丽下标对的数目

最长特殊序列 II

• 难度: easy
• 原始链接: https://leetcode.cn/problems/number-of-beautiful-pairs
• 标签: 哈希

解法一: 哈希

go

func countBeautifulPairs(nums []int) int {
  ans := 0
  countArr := make([]int, 10)
  for _, num := range nums {
    num1 := num % 10
    for j := 1; j < 10; j++ {
      if countArr[j] > 0 && gcd(j, num1) == 1 {
        ans += countArr[j]
      }
    }
    num2 := num
    for num2 >= 10 {
      num2 /= 10
    }
    countArr[num2]++
  }
  return ans
}

func gcd(num1, num2 int) int {
  if num2 == 0 {
    return num1
  }
  return gcd(num2, num1%num2)
}