# 【golang 必备算法】哈希表篇([golang essential algorithm] hash table)-go

## 【golang 必备算法】哈希表篇([golang essential algorithm] hash table)

### 242. 有效的字母异位词

``````func isAnagram(s string, t string) bool {
var m [26]int
for _,v:=range s{
m[v-'a']++
}

for _,k:=range t{
m[k-'a']--
}

for _,w:=range m{
if w!=0{
return false
}
}

return true
}
``````

### 349. 两个数组的交集

``````func intersection(nums1 []int, nums2 []int) []int {
var arr []int
h:=make(map[int]int,1)
for _,k:=range nums1{
h[k]++
}

for _,v:=range nums2{
if h[v]>0{
arr=append(arr,v)
h[v]=0
}
}

return arr
}
``````

### 202. 快乐数

``````func isHappy(n int) bool {
h:=make(map[int]int,0)

for n!=1{
if h[n]>0{
return false
}
h[n]++ //要先保存在map中，再更新
n=getsum(n)

}
return true
}

func getsum(n int)int{
sum:=0

for n>0{
sum+=(n%10)*(n%10)
n=n/10
}
return sum
}
``````

### 1. 两数之和

``````func twoSum(nums []int, target int) []int {

h:=make(map[int]int,len(nums))

for k,v:=range nums{
if p,ok:=h[target-v];ok{
return []int{k,p}
}
h[v]=k
}
return []int{}
}
``````

### 454. 四数相加 II

``````func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
h:=make(map[int]int)
var t int
for _,v1:=range nums1{
for _,v2:=range nums2{
h[v1+v2]++
}
}

for _,v3:=range nums3{
for _,v4:=range nums4{
t+=h[0-v3-v4]
}
}

return t
}
``````

### 383. 赎金信

``````func canConstruct(ransomNote string, magazine string) bool {
var mag [26]int

for _,v:=range magazine{
mag[v-'a']++
}

for _,k:=range ransomNote{
if mag[k-'a']<=0{
return false
}else{
mag[k-'a']--
}
}
return true
}
``````

### 15. 三数之和

``````func threeSum(nums []int) [][]int {
var res [][]int

sort.Ints(nums)
for i:=0;i<len(nums)-2;i++{
n1:=nums[i]
if nums[i]>0{
break
}
if i>0&&nums[i]==nums[i-1]{
continue
}

left:=i+1
right:=len(nums)-1

for right>left{
n2:=nums[left]
n3:=nums[right]

if n1+n2+n3==0{
res=append(res,[]int{n1,n2,n3})
for right>left&&nums[left]==n2{
left++
}
for right>left&&nums[right]==n3{
right--
}
}else if n1+n2+n3>0{
right--
}else if n1+n2+n3<0{
left++
}
}
}
return res
}
``````

### 18. 四数之和

``````func fourSum(nums []int, target int) [][]int {
res:=[][]int{}
if len(nums)<4{
return res
}
sort.Ints(nums)
for i:=0;i<len(nums)-3;i++{
n1:=nums[i]
if i>0&& n1 == nums[i-1] {
continue
}
for j:=i+1;j<len(nums)-2;j++{
n2:=nums[j]
if j>i+1&& n2 == nums[j-1] {
continue
}
l:=j+1
r:=len(nums)-1
for l<r{
n3:=nums[l]
n4:=nums[r]

if n1+n2+n3+n4==target{
res=append(res,[]int{n1,n2,n3,n4})
for l<r&&nums[l+1]==nums[l]{
l++
}
for  l<r&&nums[r-1]==nums[r]{
r--
}
l++
r--
}else if  n1+n2+n3+n4>target{
r--
}else{
l++
}
}
}
}
return res
}
``````
————————

### 242. Valid acronyms

``````func isAnagram(s string, t string) bool {
var m [26]int
for _,v:=range s{
m[v-'a']++
}

for _,k:=range t{
m[k-'a']--
}

for _,w:=range m{
if w!=0{
return false
}
}

return true
}
``````

### 349. Intersection of two arrays

``````func intersection(nums1 []int, nums2 []int) []int {
var arr []int
h:=make(map[int]int,1)
for _,k:=range nums1{
h[k]++
}

for _,v:=range nums2{
if h[v]>0{
arr=append(arr,v)
h[v]=0
}
}

return arr
}
``````

### 202. Happy number

Use the hash table to detect the loop, and the number that appears will directly return false

``````func isHappy(n int) bool {
h:=make(map[int]int,0)

for n!=1{
if h[n]>0{
return false
}
h[n]++ //要先保存在map中，再更新
n=getsum(n)

}
return true
}

func getsum(n int)int{
sum:=0

for n>0{
sum+=(n%10)*(n%10)
n=n/10
}
return sum
}
``````

### 1. Sum of two numbers

``````func twoSum(nums []int, target int) []int {

h:=make(map[int]int,len(nums))

for k,v:=range nums{
if p,ok:=h[target-v];ok{
return []int{k,p}
}
h[v]=k
}
return []int{}
}
``````

### 454. Adding four numbers II

``````func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
h:=make(map[int]int)
var t int
for _,v1:=range nums1{
for _,v2:=range nums2{
h[v1+v2]++
}
}

for _,v3:=range nums3{
for _,v4:=range nums4{
t+=h[0-v3-v4]
}
}

return t
}
``````

### 383. Ransom letter

``````func canConstruct(ransomNote string, magazine string) bool {
var mag [26]int

for _,v:=range magazine{
mag[v-'a']++
}

for _,k:=range ransomNote{
if mag[k-'a']<=0{
return false
}else{
mag[k-'a']--
}
}
return true
}
``````

### 15. Sum of three

Two layer cycle + double pointer

``````func threeSum(nums []int) [][]int {
var res [][]int

sort.Ints(nums)
for i:=0;i<len(nums)-2;i++{
n1:=nums[i]
if nums[i]>0{
break
}
if i>0&&nums[i]==nums[i-1]{
continue
}

left:=i+1
right:=len(nums)-1

for right>left{
n2:=nums[left]
n3:=nums[right]

if n1+n2+n3==0{
res=append(res,[]int{n1,n2,n3})
for right>left&&nums[left]==n2{
left++
}
for right>left&&nums[right]==n3{
right--
}
}else if n1+n2+n3>0{
right--
}else if n1+n2+n3<0{
left++
}
}
}
return res
}
``````

### 18. Sum of four numbers

Each layer of the cycle needs to be de duplicated

``````func fourSum(nums []int, target int) [][]int {
res:=[][]int{}
if len(nums)<4{
return res
}
sort.Ints(nums)
for i:=0;i<len(nums)-3;i++{
n1:=nums[i]
if i>0&& n1 == nums[i-1] {
continue
}
for j:=i+1;j<len(nums)-2;j++{
n2:=nums[j]
if j>i+1&& n2 == nums[j-1] {
continue
}
l:=j+1
r:=len(nums)-1
for l<r{
n3:=nums[l]
n4:=nums[r]

if n1+n2+n3+n4==target{
res=append(res,[]int{n1,n2,n3,n4})
for l<r&&nums[l+1]==nums[l]{
l++
}
for  l<r&&nums[r-1]==nums[r]{
r--
}
l++
r--
}else if  n1+n2+n3+n4>target{
r--
}else{
l++
}
}
}
}
return res
}
``````