力扣刷题第十五天--哈希表篇_C/C++

前言

情绪比较down，潦草写了一下。（敷衍读者就是敷衍自己，i know。

内容

一、快乐数

202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

用哈希集合检测循环

func ishappy(n int) bool {
     m:=map[int]bool{}
     for n!=1&&!m[n]{
         n,m[n]=getsum(n),true
     }
     return n==1
}
func getsum(n int)int{
    sum:=0
    for n>0{
        sum+=(n%10)*(n%10)
        n=n/10
    }
    return sum
}

快慢指针

如果 n 是一个快乐数，即没有循环，那么快跑者最终会比慢跑者先到达数字 1。

如果 n 不是一个快乐的数字，那么最终快跑者和慢跑者将在同一个数字上相遇。

func ishappy(n int)bool{
  slow,fast:=n,getsum(n)
  for fast!=1&&slow!=fast{
      slow=getsum(slow)
      fast=getsum(getsum(fast))
  }
  return fast==1
}
func getsum(n int)int{
    sum:=0
    for n>0{
        sum+=(n%10)*(n%10)
        n=n/10
    }
    return sum
}

二、四数相加

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

分组 + 哈希表

key：a+b的值 value：a+b的值出现的次数

遍历nums1，nums2，统计两个数组元素之和和出现的次数，放入map

遍历nums3，nums4，0-c-d在map中出现过，就把对应的value统计出来

func foursumcount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    m:=map[int]int{}
    count:=0
    for _,v1:=range nums1{
        for _,v2:=range nums2{
            m[v1+v2]++
        }
    }
    for _,v3:=range nums3{
        for _,v4:=range nums4{
           count+= m[-v3-v4]
        }
    }
    return count
}