散列

散列

理想散列表是一个包含关键字的具有固定大小的数组，它能够以常熟时间执行插入，删除和查找操作。

• 映射规则叫散列函数
• 散列冲突

冲突解决

• 拉链发
  将同一个值的关键字保存在同一个表中，查找的时候，除了根据计算出来的散列值找到对应位置外，还需要在链表上进行搜索。而在单链表上的查找速度是很慢的
• 开放定址法
  如果冲突发生，就选择另外一个可用的位置，无论是哪种开放定址法，它都要求表足够大：
  1、线性探测法，可能造成一次聚集
  2、平方探测法，可能产生二次聚集
  3、双散列，hash1(X)+2hash2(X)
• 再散列
  如果插入新的数据时散列表已满，或者散列表所剩容量不多该怎么办？这个时候就需要再散列

应用

• 文件校验
• 数字签名

两数之和（LeetCode 上第 1 号问题）

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

题目解析

使用散列表来解决该问题。
首先设置一个map容器用来记录元素的值与索引，然后遍历数组nums。

• 每次遍历时使用临时变量 tmp 用来保存目标值与当前值的差值
• 在此次遍历中查找 record，查看是否有与 tmp 一致的值，如果查找成功则返回查找值的索引值与当前变量的值。
• 如果未找到，则再 record 保存该元素与索引值 i

代码实现

func TwoSum(nums []int, t int)(int,int){
	record := make(map[int]int)
	for i:=0;i<len(nums);i++{
		tmp := t - nums[i]
		j,ok := record[tmp]
		if ok{
			return i,j
		}
		record[nums[i]] = i
	}
	return -1,-1
}

无重复字符的最长字串（ LeetCode 上第 3 号问题）

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

题目解析

建立一个HashMap，建立每个字符和其最后出现位置之间的映射，然后再定义两个变量res和left。

• res 用来记录最长无重复字串的长度
• left 指向该无重复子串左边的起始位置的前一个
  接下来遍历整个字符串，对于每个遍历到的字符，如果该字符已经在HashMap中存在了，并且如果其映射值大于 left 的话，那么更新 left 为当前映射值，然后映射值更新为当前坐标 i ，这样保证了 left 始终为当前边界的前一个位置，然后计算窗口长度的时候，直接用 i-left 即可， 用来更新结果 res。

代码更新

//利用滑动窗口
func LengthOfLongestSubstring(s string)int{
	start,end := 0,0; res := 0;n := len(s)
	//借助一个容器 来判断子串中是否有重复
	m := map[byte]byte{}
	for start < n && end < end{
		if _,ok := m[s[end]];!ok{
			m[s[end]] = s[end]
			end++ //移动滑动窗口
			res = int(math.Max(float64(res),float64(end-start)))
		}else{
				//有重复的，滑动窗口移动
				delete(m,s[start])
				start++
		}
	}
	return res
}

优化滑动窗口
func LengthOfLongestSubstring(s string)int{
	res := 0; left := -1; n := len(s)
	m := map[string]int{}
	for i := 0; i<n; i++{
		if _,ok := m[string(s[i])];ok{
			//重复的，
			left = int(math.Max(float64(m[string(s[i])]),float64(left)))
		}
		res = int(math.Max(float64(res),float64(i-left)))
		m[string(s[i])] = i
	}
	return res
}

三数之和（ LeetCode 上第 15 号问题）

题目描述

给定一个包含 n 个整数的数组 nums， 判断 nums 中是否存在三个元素a, b, c，使得a+b+c=0? 找出所有满足条件且不重复的三元组。

题目解析

一开始可以选择一个数，然后再去找另外两个数，这样只要找到两个数且和为第一个选择的数的相反数就行了。也就是需要枚举a 和 b， 将 c 存入map即可。

代码实现

func ThreeSum(nums []int)[][]int{
	sort.Ints(nums)
	n := len(nums)
	result := [][]int{}
	for i:=0;i<n-1 && nums[i]<=0; i++{
		if i>0 && nums[i] == nums[i-1]{continue}
		// j start指针， k end指针
		j := i+1; k := n-1
		t := 0-nums[i]
		for j<k{
			sum := nums[j] + nums[k]
			if sum == t{
				result = append(result,[]int{nums[i],nums[j],nums[k]})
				j++ //右移
				for j<k && nums[j-1] == nums[j]{
					j++
				}
				k-- //左移
				for j<k && nums[k+1] == nums[k]{
					k--
				}
			}else if sum>t{
				k--
				for j<k && nums[k+1] == nums[k]{
					k--
				}
			}else{
				j++
				for j<k && nums[j-1] == nums[j]{
					j++
				}
			}
		}
	}
	return result
}

最接近的三数之和（ LeetCode 上第 16 号问题）

题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

代码实现

import (
	"math"
	"sort"
)
func ThreeSumClosest(nums []int,t int)int{
	sort.Ints(nums)
	res := nums[0] + nums[1] + nums[2]
	for i:=0; i<len(nums)-2; i++{
		m,n := i+1, len(nums)-1
		for m < n{
			sums := nums[i] + nums[m] + nums[n]
			if math.Abs(float64(sums-t))<math.Abs(float64(res-t)){
				res = sums
			}
			if sums > t{
				n--
			}else if sums < t{
				m++
			}else{
				return sums
			}
		}
	}
	return res
}

重复的DNA序列（LeetCode 上第 187 号问题）

题目描述

所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。