哈希
1.两数之和：求数组中两数的和为target，返回下标。用hash，key存数，value存下标，一次遍历，每次判断hash[taget-num]是否存在，存在就返回两个下标。
https://blog.csdn.net/midi666/article/details/127170342
func twoSum(nums []int, target int) []int {
res := make(map[int]int)
for index,value := range nums {
if preIndex, ok := res[target - value]; ok {
return []int{preIndex, index}
} else {
res[value] = index
}
}
return []int{}
}
49.字母异位词分组：给定一个数组，数组中每个元素是字符串如abc，然后按照abc、acb为异位词的原则放到一个数组中，结果是个二维数组。用hash，设置一个map[[26]int][]string，每遍历到一个字符串，再遍历他的每个字符，根据数组中每个字符出现的次数的数组来当作map的key。
https://blog.csdn.net/midi666/article/details/140032365
func groupAnagrams(strs []string) [][]string {
tmpMap := make(map[[26]int][]string)
for _, str := range strs {
tmp := [26]int{}
for _, c := range str {
tmp[c-'a']++
}
tmpMap[tmp] = append(tmpMap[tmp], str)
}
ans := [][]string{}
for _, v := range tmpMap {
ans = append(ans, v)
}
return ans
}
128.最长连续序列：注意不是子序列，相当于要原数组排序后的子数组，求长度。先构造哈希表map[int]bool类型，然后遍历哈希表，如果map的[k-1]不存在，则意味着这是一个新的开始，再二层for循环判断k+1在不在，在就遍历并计数（长度++且k++），比较后取最大值。
https://blog.csdn.net/midi666/article/details/127170342
func longestConsecutive(nums []int) int {
tmpMap := make(map[int]bool)
for _, v := range nums {
tmpMap[v] = true
}
ans := 0
for key, _ := range tmpMap {
if tmpMap[key-1] == false {
long := 1
for tmpMap[key+1] {
long++
key++
}
ans = max(ans, long)
}
}
return ans
}
双指针
283.移动零：将所有的0移动到最后面。双指针，left和right都初始化为0，right小于N的循环中，只要nums[right] != 0, left和right交换，left++；然后不管怎样都right++，这样0都跑到最后去了。双指针的含义就如下：左边的指针是非0数组部分最右边的边界，右边的指针是为0数组最左边的边界，注意是不为0则进行交换。（好神奇的思路，不好理解，背吧）
https://blog.csdn.net/midi666/article/details/139945762
func moveZeroes(nums []int) {
n := len(nums)
left := 0
right := 0
for right < n {
if nums[right] != 0 {
nums[left], nums[right] = nums[right], nums[left]
left++
}
right++
}
}
11.盛水最多的容器：用线围成的边，求最大面积。双指针，从两边开始，每次取较短的那个边乘以宽度，然后比较更新最大面积，然后移动短的边界。
https://blog.csdn.net/midi666/article/details/133173678
func maxArea(height []int) int {
left := 0
right := len(height) - 1
res := 0
for left < right {
tmp := (right - left) * min(height[left], height[right])
res = max(res, tmp)
if height[left] < height[right] {
left++
} else {
right--
}
}
return res
}
15.三数之和：返回所有满足三数相加等于0的元素，搞成一个二维数组。先排序然后遍历i，在一些剪枝（包括去除i维度的重复元素）的操作后，用双指针进行处理，注意在匹配到合适的数据后，还需要处理这部分的重复元素
四题汇总
func threeSum(nums []int) [][]int {
res := [][]int{}
n := len(nums)
if n < 3 {
return res
}
sort.Ints(nums)
for i := 0; i < n-2; i++ {
// 几个异常条件
// 第一个就大于0，已经排序了，后面的都会大于0
if nums[i] > 0 {
break
}
// 去重，题目中要求了不能有重复的组合
if i > 0 && nums[i] == nums[i-1] {
continue
}
// 前三个加起来大于0了，后面的也会大于0
if nums[i]+nums[i+1]+nums[i+2] > 0 {
break
}
// 第一个数和最后的俩数加起来还小于0，直接结束这次的循环，让第一个数加点，可能还有救
if nums[i]+nums[n-1]+nums[n-2] < 0 {
continue
}
// 前面的都可以后，在这里采用左右双指针
j := i + 1
k := n - 1
for j < k {
sum := nums[i] + nums[j] + nums[k]
if sum > 0 {
k--
} else if sum < 0 {
j++
} else {
// 符合预期，先追加进结果
res = append(res, []int{nums[i], nums[j], nums[k]})
// 再分别对jk去重
j++
for j < k && nums[j] == nums[j-1] {
j++
}
k--
for j < k && nums[k] == nums[k+1] {
k--
}
}
}
}
return res
}
42.接雨水：用木板算范围，求最大面积。第一种先开辟俩数组，分别代表每个位置的前缀最大值和后缀，再遍历一遍，较小的那个减去木桶高度；第二种是双指针，left和right是遍历，pre和suf变量是前后缀最大值，用较小的那个减去木桶高度。注意这道题是前缀最大值，而不是前缀和最大值
https://blog.csdn.net/midi666/article/details/133675415
func trap(height []int) int {
n := len(height)
ans := 0
left := 0
right := n-1
preMax := 0
sufMax := 0
for left <= right {
preMax = max(preMax, height[left])
sufMax = max(sufMax, height[right])
if preMax < sufMax {
ans += preMax - height[left]
left++
} else {
ans += sufMax - height[right]
right--
}
}
return ans
}
滑动窗口
3.无重复字符的最长子串：求长度。滑动窗口+双指针，双指针求长度，定义一个固定大小的数组26[bool]当作固定大小的滑动窗口，遍历字符串，然后每次判断之前有数在数组中时，先将就窗口的left指针对应的数在窗口中改成false，然后left++来缩小左边界直到符合条件为止，然后用ans更新最大长度right-left+1
https://blog.csdn.net/midi666/article/details/138990452
func find(s string) int {
window := [26]bool{}
left := 0
ans := 0
for right, c := range s {
for window[c-'a'] {
window[s[left]-'a'] = false
left++
}
window[c-'a'] = true
ans = max(ans, right-left+1)
}
return ans
}
438.找到字符串中所有字母的异位词：s长，p短，返回这些子串的起始索引。用两个数组[26]int，来分别存两个字符串的滑动窗口，存的是字符出现的次数，先初始化p长度的，然后就比较一下；再从头开始遍历s，p窗口就永远不变了，s一进来先左边界–，再右边界++，看看是不是和p相等（数组维度相等）
https://blog.csdn.net/midi666/article/details/139282460
func findAnagrams1(s, p string) (ans []int) {
sLen := len(s)
pLen := len(p)
if sLen < pLen {
return
}
var sWindow, pWindow [26]int
for i, c := range p { // 先把p长度的数据都存进各自的滑动窗口中
sWindow[s[i]-'a']++
pWindow[c-'a']++
}
if sWindow == pWindow { // 前置位置的判断，只需要这一次判断
ans = append(ans, 0)
}
// 在这之后pWindow只是用来比较的，没有更新的场景了
for i, c := range s[:sLen-pLen] { // 从s字符串的首位开始遍历（这里减去P长度的意思是，每个窗口的大小是pLen,不减的话最后一位就越界了）
// 在这里的移动窗口，不是根据left、right来处理的，而是将当前窗口的第一个字符在数组中的位置减1
sWindow[c-'a']-- // 将窗口内对应字符的值-1
sWindow[s[i+pLen]-'a']++ // 将最后一个字符的下一个字符加1（相当于窗口整体滑动了一位）
if sWindow == pWindow {
ans = append(ans, i+1) // 如果滑动后的新窗口满足条件，将起始下标返回，此时在这个的循环中，因为已经滑动了，起始下标就是i+1
}
}
return
}
前缀和
560.和为k的子数组：给一个数组和K，求数组中和为K的子数组个数。使用前缀和+hash的思想，单独的前缀和会超时，前缀和的思路就是用一个数组来存每个位置之前的前缀和，注意一般是pre[i+1] = pre[i]+nums[i]，然后默认pre[0]=0（看题目灵活变化，也可能是pre[i] = pre[i-1] + nums[i-1]），本题中用一个变量记也可以；然后就是用hash存前缀和出现的次数，如果hash[pre-k]存在，则代表有这么多个子数组和为k。最好的办法是一次遍历，用一个变量来代表前缀和，且代码很短，注意初始化map的时候要初始{0，1}，因为在遍历的时候是从s[1]开始计算，相当于s[0] = 0。这道题二次遍历和一次遍历的方法都可以记下(直接背代码把)
另外注意前缀和一般都是下面的模板
https://blog.csdn.net/midi666/article/details/131565463
func subarraySum(nums []int, k int) (ans int) {
s := 0 // 相当于s是前缀和
cnt := map[int]int{0: 1} // s[0]=0 单独统计
for _, x := range nums {
s += x
ans += cnt[s-k] // 这里的含义是s[i] - s[j] = k 代表有一段和为k
cnt[s]++
}
return
}
栈和单调栈
239.滑动窗口最大值：给个数组，给个K，求长度为k的窗口滑动，每次滑动的最大值取出来，成数组返回。这题叫滑动窗口，用的方法却是单调栈（递减），遍历数组，先看queue数组的队尾是否小于num，否的话删队尾，直到可以入队列（入下标）。然后判断长度是不是超了，超了就出对头。然后就是每次循环只要i>=k-1就将队首加进结果数组。
https://blog.csdn.net/midi666/article/details/127185344
func maxSlidingWindow(nums []int, k int) []int {
var ans []int
var queue []int
for i, num := range nums {
// 1.入队列(元素入队尾，同时要满足队列的单调性)
for len(queue) > 0 && nums[queue[len(queue)-1]] <= num {
queue = queue[:len(queue)-1]
}
queue = append(queue, i) // 入的是下标
// 2.出队列（元素离开队首），出队列的条件是此时的下标比减去窗口起始位置的下标，大于K
if i-queue[0] >= k {
queue = queue[1:]
}
// 3.记录答案
if i >= k-1 { // 这一步主要是用于拦截最开始长度不够K的时候，比如K=3，i是下标要大于等于2的时候，才够第一个窗口
// 由于队首到队尾是单调递减，所以窗口最大值就是队首
ans = append(ans, nums[queue[0]])
}
}
return ans
}
53.最大子数组和：顾名思义。动态规划或贪心，相对简单，用变量存就行，不必要非得dp数组，先判断下之前的和加上此时的数，和单独此时数的比较，然后在维护一个最大值就行
https://blog.csdn.net/midi666/article/details/122774531
func maxSubArray(nums []int) int {
n := len(nums)
preMax := nums[0]
res := nums[0]
for i := 1; i < n; i++ {
preMax = max(preMax+nums[i], nums[i])
res = max(preMax, res)
}
return res
}
56.合并区间：给个二维数组，输出合并区间后的二维数组。先排序，一维数组的左端点排序，完事后遍历，要是已处理的右端点大于未处理的左端点，就可能可以合并，取两个的右端点较大的那个。注意排序用slices.SortFunc
https://blog.csdn.net/midi666/article/details/139760334
func merge(intervals [][]int) (ans [][]int) {
slices.SortFunc(intervals, func(p, q []int) int {
return p[0] - q[0]
})
for _, p := range intervals {
// 遍历到的每一个数组
m := len(ans)
if m > 0 && p[0] <= ans[m-1][1] { // 遍历到的左端点小于已经遍历过的右端点，可以合并
ans[m-1][1] = max(ans[m-1][1], p[1]) // 比如[[1,4], [2,3]]其实就不需要变化
} else {
ans = append(ans, p)
}
}
return
}
189.轮转数组：给个nums，给个K，1234567在k=3时变成5671234。反转三次，整体一次，左边一次，右边一次
https://blog.csdn.net/midi666/article/details/139815796
func rotate(nums []int, k int) {
k = k % len(nums)
// slices.Reverse(nums)
// slices.Reverse(nums[:k])
// slices.Reverse(nums[k:])
reverse(nums)
reverse(nums[:k])
reverse(nums[k:])
}
func reverse(nums []int) {
left := 0
right := len(nums) - 1
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
238.除自身以外数组的乘积：给定nums，返回新数组。前缀和（这个叫前缀积吧），从头到尾遍历一次，从尾到头遍历一次，每个位置的前缀积是这个位置之前的数的乘机，不要写错了，然后就是再遍历一遍，前后缀相乘
https://blog.csdn.net/midi666/article/details/139816050
func productExceptSelf(nums []int) []int {
n := len(nums)
pre := make([]int, n)
pre[0] = 1
for i := 1; i < n; i++ {
pre[i] = pre[i-1] * nums[i-1]
}
suf := make([]int, n)
suf[n-1] = 1
for i := n - 2; i >= 0; i-- {
suf[i] = suf[i+1] * nums[i+1]
}
ans := make([]int, n)
for i := 0; i < n; i++ {
ans[i] = pre[i] * suf[i]
}
return ans
}
41.缺失的第一个正整数：给一个数组，返回一个数，如果没有的话，就返回数组的下一个元素。考虑原地哈希的办法，具体思路是，在经过一系列的调整后，使得每个位置存对应这个位置的数，即nums[i] == i+1, 在i=0的时候代表第一个位置存1，若不相等，则返回i+1；为了满足这个条件，需要做的就是判断nums[i] != nums[nums[i]-1]时且0<nums[i]<n，交换（注意是for循环交换，直到满足才i++）(不好记，背把)
https://blog.csdn.net/midi666/article/details/140136149
func firstMissingPositive(nums []int) int {
n := len(nums)
for i := 0; i < n; i++ {
for nums[i] > 0 && nums[i] < n && nums[i] != nums[nums[i]-1] {
nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
}
}
for i := 0; i < n; i++ {
// 如果当前元素不等于它的索引+1,那索引+1就是第一个缺失的正整数
if nums[i] != i+1 {
return i + 1
}
}
// 没有的话，缺失的正整数就是数组长度+1
return n + 1
}
73.矩阵置零：给定二维数组，返回原数组。开两个bool类型的row和col数组，遍历原数组，只要一个元素为0，两个数组的这一行（列）都为0。重新遍历原数组，只要有对应的行列为0，遍历到的这个元素就为0
https://blog.csdn.net/midi666/article/details/139668417
func setZeroes(matrix [][]int) {
row := make([]bool, len(matrix))
col := make([]bool, len(matrix[0]))
for i, r := range matrix {
for j, v := range r {
if v == 0 {
row[i] = true
col[j] = true
}
}
}
for i, r := range matrix {
for j := range r {
if row[i] || col[j] {
r[j] = 0
}
}
}
}
54.螺旋矩阵：给定二维矩阵m*n，输出一维矩阵，要顺时针输出。
三题合一
func spiralOrder(matrix [][]int) []int {
rows := len(matrix)
columns := len(matrix[0])
top, bottom := 0, rows -1
left, right := 0, columns -1
res := make([]int, 0)
nums := rows*columns
for nums >= 1 {
for i := left; i <= right && nums >= 1; i++ {
res = append(res, matrix[top][i])
nums--
}
top++
for i := top; i <= bottom && nums >= 1; i++ {
res = append(res, matrix[i][right])
nums--
}
right--
for i := right; i >= left && nums >= 1; i-- {
res = append(res, matrix[bottom][i])
nums--
}
bottom--
for i := bottom; i >= top && nums >= 1; i-- {
res = append(res, matrix[i][left])
nums--
}
left++
}
return res
}
48.旋转图像：给定二维数组，顺时针旋转90度。先主对角线反转，再水平反转
三题和一
func rotate(matrix [][]int) {
//图片一般都是n*n的
n := len(matrix)
//水平翻转
for i := 0; i < n/2; i++ {
matrix[i], matrix[n-1-i] = matrix[n-1-i], matrix[i]
}
//主对角线翻转
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
}
}
}
74.搜索二维矩阵I：每行递增，每列递增，且下一列的开头元素还大于上一列的结尾，判断target是否存在。这道题用上面的解法也能实现，但实际上是用二分法，left := 0, right := m*n, 然后算出来mid，x := matrix[mid/n][mid%n]，再比较大小。n其实是一维矩阵中元素的个数，除以n就是第几行，取余n就是第几列
https://blog.csdn.net/midi666/article/details/139376973
func searchMatrix(matrix [][]int, target int) bool {
m := len(matrix)
n := len(matrix[0])
left := 0
right := m * n
for left < right {
mid := left + (right-left)/2
x := matrix[mid/n][mid%n]
if x == target {
return true
} else if x < target {
left = mid + 1
} else {
right = mid
}
}
return false
}
240.搜索二维矩阵II：每行递增，每列递增，给target，判断是否存在。从右上角开始，若右上角小于target，则排除整行；小于则排除整列。
https://blog.csdn.net/midi666/article/details/139668235
func searchMatrix(matrix [][]int, target int) bool {
m := len(matrix)
n := len(matrix[0])
i, j := 0, n-1 // 从右上角开始
for i <= m-1 && j >= 0 { // 还有剩余元素
if matrix[i][j] == target {
return true
}
if matrix[i][j] < target {
i++
} else {
j--
}
}
return false
}
