一般要记住，
1.二分会得到O(logn)的时间复杂度；
2.可以先想想是否可以使用快慢指针

1.给定一个数组，数组中两个数相加为一个值的组合

暴力法O(n^2)：嵌套循环遍历数组

var result []int
for index1, num1 := range nums {
    for index2, num2 := range nums {
        if index1 != index2 && num1+num2 == target {
            result = append(result, num1)
            result = append(result, num2)
            goto stop
        }
    }
}
stop:
      return result

哈希法O(n)一次遍历：

var result []int
hash := make(map[int]int)
var want int
for index, num := range nums {
    want = target - num
    position, ok := hash[want]
    if ok != false {
        result = append(result, nums[position])
        result = append(result, nums[index])
        break
    }
    hash[num] = index
}
return result

2.查找两个有序数组的中位数

暴力解法：求出两个数组个数之和n,循环判断a[i],b[j]大小并取出更小的那个，直到n/2（考虑n的奇偶性）时间复杂度为O(m+n)
利用中位数的性质：中位数左右两边元素个数相同，并且左子集的最大值小于右子集的最小值时间复杂度为O(log(m+n))

3.给定一个数组，查找盛水最多的区间

暴力解法：嵌套循环求出最大面积
双指针法：盛水的面积取决于区间a,b长度 * nums[a]和nums[b]的更小值,如果向内移动长板，则面积一定不会变大。如果向内移动短板，则面积有可能会变大。

func getMax(nums []int) int {
    i, j := 0, len(nums)-1
    max := 0
    var temp int
    for i < j {
        temp = (j - i) * min(nums[i], nums[j])
        if temp > max {
            max = temp
        }
        if nums[i] < nums[j] {
            i++
        } else {
            j--
        }
    }
    return max
}

4.找出给定数组中，三个数相加为0的所有组合

暴力解法:三层嵌套循环遍历出所有组合，时间复杂度为O(n^3)
hash解法：模拟第一题的做法，时间复杂度为O(n^2)，但是空间复杂度过大
排序+双指针法：现将数组排序，遍历排序的数组，如果nums[a]大于0可知，nums[a]与后面的数的组合不可能为0；如果nums[a]与nums[a-1]则跳过，因为在遍历到nums[a-1]时已经寻找解法了。时间复杂度为O(n^2)

func getRes(nums []int) [][]int {
    var res [][]int
    var left int
    var right int
    sort.Ints(nums)
    for index, num := range nums {
        if num > 0 {
            break
        }
        if index > 0 && num == nums[index-1] {
            continue
        }
        left = index + 1
        right = len(nums) - 1
        for left < right {
            if nums[left]+nums[right]+num == 0 {
                res = append(res, []int{num, nums[left], nums[right]})
                for left < right && nums[left] == nums[left+1] {
                    left++
                }
                for left < right && nums[right] == nums[right-1] {
                    right--
                }
                left++
                right--
            } else if nums[left]+nums[right]+nums[index] < 0 {
                left++
            } else {
                right--
            }
        }
    }
    return res
}

该题可变种为
1.最接近target的组合，解法相同只需要将判断 == 0改造即可
2.四个数之和为target的组合，需要固定两个数之后移动后两个数，为三层嵌套循环，时间复杂度为O(n^3)

5.原地删除有序数组的重复值

快慢指针法

func getRes(nums []int) ([]int, int) {
    if len(nums) <= 1 {
        return nums, len(nums)
    }
    slow := 0
    fast := slow + 1
    for fast < len(nums) {
        if nums[fast] != nums[slow] {
            slow++
            nums[slow] = nums[fast]
        }
        fast++
    }
    return nums, slow
}

5.原地删除有序数组的重复值

快慢指针

func getRes(nums []int, target int) []int {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != target {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return nums
}

变种:保留重复的最多2个

func removeDuplicates(nums []int) int {
    fast := 2
    slow := 1
    for fast < len(nums) {
        if nums[fast] != nums[slow - 1] {
            slow ++
            nums[slow] = nums[fast]
        }
        fast ++
    }
    return slow + 1
}

6.给定一个数组返回其字典序的下一个排列（例如1， 3， 2返回2，1， 3）

从数组最后开始向前遍历，找到一个nums[i] > nums[i - 1]的i，从右向左继续查找j是的nums[j] > nums[i],找到后i与j交换，并将i之后的部分翻转

func getRes(nums []int) []int {
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i --
    }
    if i >= 0 {
        j := len(nums) - 1
        for j >= 0 && nums[j] <= nums[i] {
            j --
        }
        swap(nums, i, j)
    }
    reverse(nums, i+1)
    return nums
}

7.某个有序数组从中间一个位置进行了翻转，即该位置的左右两半部分调换，从中取出一个target并得到他的index

该题时间复杂度要求为O(logn)，必然是二分查找了

func getRes(nums []int, target int) int {
    start := 0
    end := len(nums) - 1
    var position int
    for start <= end {
        mid := start + (end-start)/2
        if nums[mid] == target {
            position = mid
            break
        }
        if nums[mid] >= nums[start] {
            if nums[start] <= target && nums[mid] >= target {
                end = mid - 1
            } else {
                start = mid + 1
            }
        } else {
            if nums[end] >= target && nums[mid] <= target {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    }
    return position
}

变种：如果这个有序数组中可以有重复数值
这种情况主要是对于nums[mid] == nums[start]情况不好判断应该取前半部分还是后半部分，例如10111111 和 11111011这两种我们并不知道0在前半部分还是后半部分，所以直接start ++即可。

func search(nums []int, target int) bool {
    start := 0
    end := len(nums) - 1
    for start <= end {
        mid := start + (end-start)/2
        if nums[mid] == target {
            return true
        }
        if nums[mid] == nums[start] {
            start ++
        } else if nums[mid] > nums[start] {
            if nums[start] <= target && nums[mid] >= target {
                end = mid - 1
            } else {
                start = mid + 1
            }
        } else {
            if nums[end] >= target && nums[mid] <= target {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    }
    return false 
}

变种：求出最小值

func findMin(nums []int) int {
    left := 0
    right := len(nums) - 1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] < nums[mid - 1] {
            return nums[mid]
        }
        if nums[mid] > nums[mid + 1] {
            return nums[mid + 1]
        }
        if (nums[mid] > nums[left]) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

func findMin(nums []int) int {
    left := 0
    right := len(nums) - 1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] < nums[right] {
            right = mid
        } else {
            left = mid + 1
        } 
    }
    return nums[right]
}

变种：带有重复的元素的最小值

func findMin(nums []int) int {
    left := 0
    right := len(nums) - 1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] < nums[right] {
            right = mid
        } else if nums[mid] > nums[right]{
            left = mid + 1
        } else {
            right = right - 1
        }
    }
    return nums[left]
}

8.在一个有序可重复数组中查找某个值开始的位置和结束的位置

可以暴力做，时间复杂度为O(n)
如果要时间复杂度更低，那就是O(logn)，那基本上就是二分了
先二分找最左，再二分找最右，两次二分就可以了

9.在一个有序数组中查找一个target，若找到则返回index，若未找到则返回插入的index

func getRes(nums []int, target int) int {
    start := 0
    end := len(nums) - 1
    var mid int
    for start <= end {
        mid = start + (end-start)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    //如果没找到target，则跳出循环时end + 1 = start,有两种情况可能会导致这种情况，一种是end - 1，另一种是start + 1，
    //不管是哪一种，最后target插入的位置都是最后的start位置（可以举例验证）
    return start
}

10.找出无序数组中所有满足和为target的组合（可以重复使用）

先考虑一下回溯：把所有的路都走一遍然后再剪个枝？试一下
先把nums排序

func getRes(start int, path []int, now, target int) {
    if now == target {
        res = append(res, path)
    } else if now < target {
        //为了防止重复组合,所以每次都不回再向前寻找而是从start开始向后寻找
        for i := start; i < len(nums); i++ {
            getRes(i, append(path, nums[i]), now+nums[i], target)
        }
    } else {
        return
    }
}

好像不需要用动态规划，不太好找出动态规划方程式，而且不会有重复状态，用了动态规划没啥意义

变种：如果不能重复使用

func getRes(start int, path, nums []int, now, target int) {
    if now == target {
        res = append(res, path)
    } else if now < target {
        //为了防止重复组合,所以每次都不回再向前寻找而是从start开始向后寻找
        for i := start; i < len(nums); i++ {
            if i > start && nums[i] == nums[i - 1]{
                continue
            }
            getRes(i + 1, append(path, nums[i]), nums, now+nums[i], target)//在这里控制不使用自己就好了...
        }
    } else {
        return
    }
}

11.给定一个未排序数组，找到其中未出现的最小正整数

看起来要排序，但是这样再遍历的时间复杂度就是O(nlogn)了，
如果要在O(n)下完成的话需要借助一些辅助空间了，首先考虑的是hash散列表，将所有值都在hash中（hash的key是值，value是数组的index）,然后从1开始从hash遍历，哪个没有就是哪个了，但是这个空间复杂度就不好说了
借助数组：

func getRes(nums []int) int {
    //建立辅助数组，最小未出现的正整数一定不会比nums的长度多,其他大于nums长度的数字就不用管了
    tmp := make([]bool, len(nums)+1)
    for _, value := range nums {
        if value < len(nums)+1 {
            tmp[value] = true
        }
    }
    var pos int
    fmt.Println(tmp[1])
    for i := 1; i < len(tmp); i++ {
        if !tmp[i] {
            pos = i
            break
        }
    }
    return pos
}

12接雨水

image.png

暴力解法：每一个位置能够盛的水量为它左边最大值和右边最大值其中的最小值，当然这个最小值必须要比自己位置要高！时间复杂度为O(n^2)
可以发现，在这种做法中，其实有很多重复计算的问题，在每一个位置都需要向左和向右遍历一遍导致时间复杂度上升

func getRes(nums []int) int {
    left := make([]int, len(nums))
    right := make([]int, len(nums))
    var leftMax int
    var rightMax int
    for i := 1; i < len(nums); i++ {
        left[i] = max(nums[i], leftMax)
    }
    for i := len(nums) - 2; i >= 0; i-- {
        right[i] = max(nums[i], rightMax)
    }
    res := 0
    for i := 1; i < len(nums)-1; i++ {
        res += min(left[i], right[i]) - nums[i]
    }
    return res
}

13.给定一个数组，数组中每一个元素都是从该位置能够跳的步数，求最少需要多少步可以到达末尾

贪心算法：遍历数组，每次都将所处位置能够到达的位置与现在能够到达的位置相比较。

func getRes(nums []int) int {
    maxPosition := 0
    step := 0
    stop := 0
    //这里只判断到倒数第二个数字，因为如果正好到达了最后一个的话还会step++，所以只需要到达倒数第二个
    for index := 0; index < len(nums)-1; index++ {
        maxPosition = max(index+nums[index], maxPosition)
        if index == stop {
            step++
            stop = maxPosition
        }
    }
    return step
}

动态规划:

变种：只求能不能到达末尾

func getRes(nums []int) bool {
    maxPosition := 0
    for index := 0; index < len(nums)-1; index++ {
        maxPosition = max(index+nums[index], maxPosition)
        if maxPosition == index {
            return false
        }
    }
    return true
}

14.原地旋转二维数组，顺时针旋转90度

先对角线（左上到右下）翻转，再竖直翻转

func getRes(nums [][]int) {
    for i := 0; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            temp := nums[i][j]
            nums[i][j] = nums[j][i]
            nums[j][i] = temp
        }
    }
    for i := 0; i < len(nums); i++ {
        for j := 0; j < len(nums)/2; j++ {
            temp := nums[i][j]
            nums[i][j] = nums[i][len(nums)-1-j]
            nums[i][len(nums)-1-j] = temp
        }
    }
    fmt.Println(nums)
}

15.给定一个数组，求出具有最大和的连续子数组

动态规划没得商量,时间复杂度为O(n)

//正经动态规划
func getRes(nums []int) int {
    dp := make([]int, len(nums))
    //dp[i]代表以i为结尾的最大子序列
    dp[0] = nums[0]
    maxRes := nums[0]
    for i := 1; i < len(nums); i++ {
        dp[i] = max(dp[i-1]+nums[i], nums[i])
        if maxRes < dp[i] {
            maxRes = dp[i]
        }
    }
    return maxRes
}
//减少辅助空间的动态规划
func getRes(nums []int) int {
    sum := 0
    res := nums[0]
    for _, value := range nums {
        if sum > 0 {
            sum = sum + value
        } else {
            sum = value
        }
        res = max(res, sum)
    }
    return res
}

16. 求m*n的二维数组按照顺时针螺旋的序列

func getRes(nums [][]int) []int {
    m := len(nums)
    n := len(nums[0])
    row := []int{0, 1, 0, -1}
    col := []int{1, 0, -1, 0}
    res := make([]int, m*n)
    nowR := 0
    nowC := 0
    seen := make([][]bool, m)
    di := 0
    for i := 0; i < m; i++ {
        seen[i] = make([]bool, n)
    }
    fmt.Println(seen)
    for i := 0; i < n*m; i++ {
        res[i] = nums[nowR][nowC]
        seen[nowR][nowC] = true
        nextR := nowR + row[di]
        nextC := nowC + col[di]
        if nextC >= 0 && nextC < n && nextR >= 0 && nextR < m && !seen[nextR][nextC] {
            nowR = nextR
            nowC = nextC
        } else {
            di = (di + 1) % 4
            nowR = nowR + row[di]
            nowC = nowC + col[di]
        }
    }
    return res
}

17.m*n的网格中从0，0到m-1, n-1的所有路径

动态规划不解释

func getRes(m, n int) int {
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 || j == 0 {
                dp[i][j] = 1
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
    return dp[m-1][n-1]
}

变种：如果输入的二维数组中如果值为1则代表有障碍物

func getRes(nums [][]int) int {
    dp := make([][]int, len(nums))
    for i := 0; i < len(nums); i++ {
        dp[i] = make([]int, len(nums[0]))
    }
    for i := 0; i < len(nums); i++ {
        for j := 0; j < len(nums[0]); j++ {
            if i == 0 && j == 0 {
                dp[i][j] = 1
            } else if i == 0 {
                if nums[i][j] == 1 {
                    dp[i][j] = 0
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            } else if j == 0 {
                if nums[i][j] == 1 {
                    dp[i][j] = 0
                } else {
                    dp[i][j] = dp[i-1][j]
                }
            } else {
                if nums[i][j] == 1 {
                    dp[i][j] = 0
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                }
            }
        }
    }
    return dp[len(nums)-1][len(nums[0])-1]
}

变种:给定一个二维数组，找出一条左上角到右下角的最小路径

func getRes(nums [][]int) int {
    dp := make([][]int, len(nums))
    for i := 0; i < len(nums); i++ {
        dp[i] = make([]int, len(nums[0]))
    }
    for i := 0; i < len(nums); i++ {
        for j := 0; j < len(nums[0]); j++ {
            if i == 0 && j == 0 {
                dp[i][j] = nums[i][j]
            } else if i == 0 {
                dp[i][j] = dp[i][j-1] + nums[i][j]
            } else if j == 0 {
                dp[i][j] = dp[i-1][j] + nums[i][j]
            } else {
                dp[i][j] = nums[i][j] + min(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[len(nums)-1][len(nums[0])-1]
}

18.给定一个数组，数组只有0，1，2三种元素，将数组从小到大排列

计数排序，遍历一次数组即可
快排改造算法，可降低空间复杂度

func getRes(nums []int) []int {
    left := 0
    right := len(nums) - 1
    for left < right {
        fmt.Println(left)
        fmt.Println(right)
        //left不等于0，right不等于2
        for left < right && nums[left] == 0 {
            left++
        }
        for left < right && nums[right] == 2 {
            right--
        }
        if left >= right {
            break
        }
        if nums[left] == 1 && nums[right] == 0 {
            swap(nums, left, right)
            left++
            continue
        }
        if nums[left] == 1 && nums[right] == 1 {
            temp := left
            for temp < right {
                if nums[temp] == 0 {
                    swap(nums, temp, left)
                    break
                }
                temp++
            }
            left = temp + 1
            continue
        }
        if nums[left] == 2 && nums[right] == 0 {
            swap(nums, left, right)
            left++
            right--
        }
        if nums[left] == 2 && nums[right] == 1 {
            swap(nums, left, right)
            right--
        }
    }
    return nums
}

19.给定一个不重复的数组，求所有可能的子集

回溯

func getRes(start int, tmp []int) {
    res = append(res, tmp)
    for i := start; i < len(nums); i++ {
        getRes(i+1, append(tmp, nums[i]))
    }
}

变种:数组中有重复的元素，求所有不重复的子集

func getRes(start int, tmp []int) {
    res = append(res, tmp)
    for i := start; i < len(nums); i++ {
        if i != start && nums[i] == nums[i-1] {
            continue
        }
        getRes(i+1, append(tmp, nums[i]))
    }
}

20.给定一个二维字符数组和一个字符串，判断二维数组中是否能找到这个字符串

回溯回溯回溯，重要的事情讲三遍！

func exist(board [][]byte, word string) bool {
    visited := make([][]bool, len(board))
    for i := 0; i < len(board); i ++ {
        visited[i] = make([]bool, len(board[0]))
    }
    for i := 0; i < len(board); i ++ {
        for j := 0; j < len(board[0]); j ++ {
            if dfs(visited, board, word, i, j) {
                return true
            }
        }
    }
    return false
}

func dfs(visited [][]bool, board [][]byte, word string, now_row, now_col int) bool {
    if len(word) == 1 {
        if board[now_row][now_col] == word[0] {
            return true
        } else {
            return false
        }
    }

    d_row := [4]int{-1, 0, 1, 0}
    d_col := [4]int{0, 1, 0, -1}
    if board[now_row][now_col] == word[0] {
        visited[now_row][now_col] = true
        for i := 0; i < 4; i ++ {
            new_row := now_row + d_row[i]
            new_col := now_col + d_col[i]
            if 0 <= new_row && new_row < len(board) && 0 <= new_col && new_col < len(board[0]) && !visited[new_row][new_col] {
                if dfs(visited, board, word[1:], new_row, new_col) { 
                    return true
                }
            }
        }
    }
    visited[now_row][now_col] = false
    return false  
}

21.给定一个数组(有正有负)，求出乘机最大的子序列

func maxProduct(nums []int) int {
    dpMin := make([]int, len(nums))
    dpMin[0] = nums[0]
    dpMax := make([]int, len(nums))
    dpMax[0] = nums[0]
    max := nums[0]
    for i := 1; i < len(nums); i ++ {
        dpMax[i] = maxFind(dpMax[i-1] * nums[i], maxFind(dpMin[i-1]*nums[i], nums[i]))
        dpMin[i] = minFind(dpMin[i-1] * nums[i], minFind(dpMax[i-1]*nums[i], nums[i]))
        if dpMax[i] > max {
            max = dpMax[i]
        }
    }
    return max
}

21旋转数组，向右移动k个字符

将数组前n-k个字符翻转，将数组后k个翻转，再将整个数组翻转

func rotate(nums []int, k int)  {
    k = k % len(nums)
    reverse(nums, 0, len(nums) - k - 1)
    reverse(nums, len(nums) - k, len(nums) - 1)
    reverse(nums, 0, len(nums) - 1)
}

func reverse(nums []int, start, end int) {
    for start < end {
        temp := nums[start]
        nums[start] = nums[end]
        nums[end] = temp
        start ++
        end --
    }
}