注意，这些代码我都会用GO来进行实现，参考：

想去看机会？这10道最高频的手撕代码题都会了吗？ - 云+社区 - 腾讯云 (tencent.com) (opens new window)

快速排序

这个非常的经典，必须要熟练掌握才行，具体代码如下

// 快速排序-返回枢纽位置并进行排序，传入一个low指针，一个high指针，然后给数组进行简单排序
// 这里我们的数组排序好后返回一个中间位置的指针
func partition(arr []int,low int,high int) int {
   // 一般情况下我们直接取low点作为枢纽，然后我们就要进行排序，把比low小的排左边，比low大的排右边
   tmp:=arr[low]
   // 当low大于high时我们的排序就已经好了,这个时候其实low就是high同时这个值为我们的枢纽
   for low < high {
      // 首先我们从high哪里往左遍历，找出第一个比tmp小的点
      for low < high && arr[high] >= tmp {
         high --
      }
      // 找到这个比tmp小的点后我们就替换过去，这个时候我们的high其实留了一个空
      arr[low] = arr[high]
      // 因为上面high有一个空，所以这时候我们就可以从low指针开始出发，找到一个比tmp大的
      for low < high && arr[low] <= tmp {
         low ++
      }
      // 找到后我们就可以替换了，这个时候我们就把high给替换了，此时low就没用了
      // 然后我们就可以进行下一轮比较了，然后我们可以继续把比tmp小的点放到low这里
      arr[high] = arr[low]
   }
   // fmt.Println(low,high)
   // 最后替换完后，low和high其实就指向同一个位置了，这时我们就可以把low换成tmp了
   arr[low] = tmp
   // 返回low指针
   return low
}
// 快速排序
// 时间复杂度 nlogn 这东西推导比较复杂
// 具体参考 https://www.zhihu.com/question/22393997
// 空间复杂度 最好情况nlogn（注意这个log以2为底），最坏情况就是n
func quickSort(arr []int,low int,high int)  {
   // 这里也要判断，要不然会堆栈溢出
   if low < high {
      // 给数组进行简单排序，同时留下一个mid位置的指针
      mid:=partition(arr,low,high)
      // 这里我们使用递归来分别递归左右两部分
      quickSort(arr,low,mid-1)
      quickSort(arr,mid+1,high)
   }
}

二分查找

这个也非常经典，废话不多说，直接贴代码，这题比较简单，我就不写注释了哈哈，这里要注意low和high的取值

func binarySearch(arr []int,target int) bool {
   low:=0;high:=len(arr)-1
   for low <= high {
      mid:=(low+high)/2
      if arr[mid] > target {
         high = mid -1
      } else if arr[mid] < target {
         low = mid +1
      } else {
         return true
      }
   }
   return false
}
// 测试类如下
func Test_binary(t *testing.T) {
	fmt.Println(binarySearch([]int{0,5,16,20,27,30,36,44,55,60,67,71},72))
}

爬楼梯

这个是一道非常经典的动态规划的题目，必须掌握

70. 爬楼梯 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

// 爬楼梯问题
func climbStairs(n int) int {
   if n == 1 {
      return 1
   }
   if n == 2 {
      return 2
   }
   // a表示第一阶，b表示第二阶，后面a就表示n-2 b表示n-1
   a:=1
   b:=2
   // sum就表示总数
   sum:=0
   // 然后我们就可以计算每一阶的了
   for i:=3;i<=n;i++ {
      sum = a+b
      a=b
      b=sum
   }
   return sum
}

两数之和

千万不要用两层for循环，我们可以使用hash表来存储数据，这样就避免两层for循环了

1. 两数之和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

func twoSum(nums []int, target int) []int {
	// 我们使用hash来存储数据
	hash:=make(map[int]int,len(nums))
	// 遍历整个数组
	for i := 0; i < len(nums); i++ {
		tmp:=target-nums[i]
		// 判断这个值是否在map中
		if _, ok := hash[tmp]; ok {
			// 如果在就直接返回值
			return []int{hash[tmp],i}
		} else {
			// 如果不在那么就放入hash中
			hash[nums[i]] = i
		}
	}
	// 没有就返回空
	return []int{}
}

最大回撤（最大利润）

剑指 Offer 63. 股票的最大利润 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题目其实就是找到一个最小价格买入，然后一个最大价格卖出即可

func maxProfit(prices []int) int {
   // 如果长度只是1，那么我们就返回0
   if len(prices) <= 1 {
      return 0
   }
   // 记录一个最小值和最大利润
   minPrice:=math.MaxInt32
   maxProfile:=0
   // 开始遍历数组进行计算
   for i := 0; i < len(prices); i++ {
      // 先找到一个最小价格买入
      if prices[i] < minPrice {
         minPrice = prices[i]
      } else if prices[i]-minPrice > maxProfile {
         // 然后我们以最大价格卖出
         maxProfile = prices[i]-minPrice
      }
   }
   return maxProfile
}

合并两个有序数组

这个题目主要是考归并排序的思想，我在leetcode上找到一个类似的题目

88. 合并两个有序数组 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这个我们可以使用逆向思维，我们倒着进行排序

func merge(nums1 []int, m int, nums2 []int, n int)  {
	// 使用i来表示当前数组的结尾
	i:=len(nums1)-1;m--;n--
	// 我们从后往前进行遍历
	for m>=0 && n>=0 {
        // 找到一个大的然后进行插入
		if nums1[m] > nums2[n] {
			nums1[i] = nums1[m]
			m--
		} else {
			nums1[i] = nums2[n]
			n--
		}
		i--
	}
	// 判断n是否排序完毕
	for n>=0 {
		nums1[i] = nums2[n]
		i--;n--
	}
}

合并链表

21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一： 使用递归

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
   // 判断当前l1是否为空，为空就返回另一个链表
   if l1 == nil {
      return l2
   } else if l2 == nil {
      return l1
   } else if l1.Val < l2.Val {
      // 如果l1更小，那么我们就合并l2
      l1.Next = mergeTwoLists(l1.Next,l2)
      return l1
   } else {
      l2.Next = mergeTwoLists(l1,l2.Next)
      return l2
   }
}

最大连续子数组之和

这个题目也是一个经典的动态规划的题目

剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

我们这里要注意这个子数组是连续的

// 连续子数组的最大和
func maxSubArray(nums []int) int {
	// 默认情况下，我们的最大值就是第0号
	res:=nums[0]
	// 下面我们开始顺序遍历
	for i:=0;i<len(nums);i++{
		// 这个地方是关键，看自己理解了
		nums[i] += max(nums[i-1],0)
		// 最后我们求一个最大值
		res = max(res,nums[i])
	}
	return res
}
// 求最大值
func max(a int,b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

最长不重复子串

3. 无重复字符的最长子串 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题的难度就比较大了，主要有下面这两个解法

滑动窗口

我们维护一个窗口，确保输入的值是在范围内的

func lengthOfLongestSubstring(s string) int {
	// 使用一个map来存储位置信息
	data:=make(map[byte]int)
	// n表示s的长度
	n:=len(s)
	// 声明一个右指针表示起始第一个，然后ans表示最大的长度
	rk,ans:=0,0
	for i:=0;i<n;i++{
		if i != 0 {
			// 我们尝试删除前一个元素，然后再进行遍历判断
			delete(data,s[i-1])
		}
		// 如果右指针小于s的长度，并且当前位置也没重复的话,我们就移动一下右指针
		for rk < n && data[s[rk]] == 0 {
			data[s[rk]]++
			rk++
		}
		// 最后我们就可以统计一下长度了
		ans = max(ans,rk-i)
	}
	return ans
}

动态规划

看了一下别人的代码，感觉这个不太友好。。

全排序

46. 全排列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

我擦，这题居然被我做出来了，真的是可喜可贺，这题其实不难

// 全排列问题
func permute(nums []int) [][]int {
   var data [][]int
   getOrder(nums,0,&data)
   return data
}

// 我们需要使用一个辅助数组来存储数据
func getOrder(nums []int,index int,ans *[][]int) {
   // 当我们的index等于nums时，结束循环
   if index == len(nums)-1 {
      tmp:=make([]int,len(nums))
      copy(tmp,nums)
      *ans = append(*ans, tmp)
      return
   }
   // 然后我们开始进行排序
   for i := index; i < len(nums); i++ {
      nums[index],nums[i] = nums[i],nums[index]
      getOrder(nums,index+1,ans)
      nums[index],nums[i] = nums[i],nums[index]
   }
}

全排列去重

上面那个是不包含重复的情况，下面是存在重复的情况

剑指 Offer 38. 字符串的排列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

去重可以考虑使用map来存储位置信息，判断是否出现过了，如果出现了，就不排序

// 全排列问题,去重问题
func permutation(s string) []string {
   var ans []string
   dfs([]byte(s),0,&ans)
   return ans
}

func dfs(s []byte,k int,ans *[]string)  {
   // 到达结束条件时添加到结果中
   if k == len(s)-1 {
      *ans = append(*ans, string(s))
      return
   }
   // 使用map来保存数据
   tmp:=make(map[byte]bool)
   // 遍历剩下的部分
   for i:=k;i<len(s);i++ {
      // 判断是否排序过了，如果排序过了，我们就不排序
      if !tmp[s[i]] {
         tmp[s[i]] = true
         s[k],s[i] = s[i],s[k]
         dfs(s,k+1,ans)
         s[k],s[i] = s[i],s[k]
      }
   }
}

三数之和

15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题使用三指针法，注意我们必须要提前排好序，这样才方便查找

func threeSum(nums []int) [][]int {
   // 数组的长度
   n := len(nums)
   // 给数组进行排序
   sort.Ints(nums)
   // 最后的排序结果
   ans := make([][]int, 0)
   // 开始进行遍历,这个是第一个指针
   for k := 0; k < n-2; k++ {
      // 首先判断k是否小于或者等于0，如果不是我们就跳出循环
      // 因为我们的数组实际上是已经排好序了的，所以我们k一定是小于或者等于0的
      if nums[k] > 0 { break }
      // 如果遇到相等的，我们可以先跳过，因为相等的我们已经计算过了，不需要重复计算
      if k > 0 && nums[k] == nums[k-1] { continue }
      // i表示第二个指针，j表示第三个指针
      i:=k+1;j:=n-1
      for i < j {
         // 先计算一下和
         sum:=nums[k]+nums[i]+nums[j]
         // 如果当前小于0，我们可以移动一下i指针，当然我们还需要考虑指针相等的情况
         if sum < 0 {
            for i<j && nums[i]==nums[i+1] {i++}
            // 我们无论如何都要+1操作，因为上面那个for循环可能不执行
            i++
         } else if sum >0{
            for i<j && nums[j]==nums[j-1] {j--}
            j--
         }else {
            ans = append(ans, []int{nums[k],nums[i],nums[j]})
            // 我们继续寻找下一个
            for i<j && nums[i]==nums[i+1] {i++}
            for i<j && nums[j]==nums[j-1] {j--}
            i++
            j--
         }
      }
   }
   return ans
}