Posts

数组中的第K个最大元素 题目 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例 1: 1 2 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例2： 1 2 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明: 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。 思路 简单无脑：排序后取第K大 优化：使用快排，中途找到第K的时候就可以提前退出了 解答 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 func findKthLargest(nums []int, k int) int { return quickSort(nums, 0, len(nums)-1, k) } func quickSort(nums []int, low, high, k int) int { if low == high { return nums[low] } pos := partition(nums, low, high) // 满足情况，第K大 if pos == len(nums)-k { return nums[pos] } if pos < len(nums)-k { return quickSort(nums, pos+1, high, k) } return quickSort(nums, low, pos-1, k) } func partition(nums []int, low, high int) int { // 1. 选取枢纽值（low应该替换为随机数） pos := nums[high] for low <= high { // 2. 低指针上移，不符合条件式替换到nums[high] for low < high && nums[low] <= pos { low++ } nums[high] = nums[low] // 3. 高指针下移，不符合条件时替换到nums[low] for low < high && nums[high] >= pos { high-- } nums[low] = nums[high] } // 归位，low最后移动，所以觉定最终位置 nums[high] = pos return high } // 执行用时 :12 ms, 在所有 Go 提交中击败了55.08%的用户 // 内存消耗 :4 MB, 在所有 Go 提交中击败了26.32%的用户

反转链表 题目 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 遍历和递归 遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 func reverseList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } p := head.Next // 工具人游标 head.Next = nil // 摘下头节点准备迎接 for p != nil { tmp := p.Next // 作好后期计划 p.Next = head // 斩断后继无牵挂 head = p // 抢回第一把交椅 p = tmp // 重拾信心，继续前进 // 丧心病狂的写法： // p.Next, head, p = head, p, p.Next } return head } // 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户 // 内存消耗 :2.5 MB, 在所有 Go 提交中击败了100.00%的用户 向着header前进！！！！ ...

十、并发编程 并发与并行 并发：同一 时间段内 执行多个任务（用微信和两个人聊天） 并行：同一 时刻 执行多个任务（你和你朋友都在用微信和别人聊天） Go并发通过goroutine实现 goroutine类似线程，用户态线程，可以根据需要创建成千上万个 goroutine是Go语言运行时（runtime）调度完成，而线程是由操作系统调度完成 Go提供channel在多个goroutine间通信 goroutine 定义多个任务，让系统帮助这些任务分配到CPU上实现并发执行 goroutine类似线程，Go语言运行时（runtime）调度完成。Go程序会智能地将 goroutine 中的任务合理地分配给每个CPU。语言层面内置了调度和上下文切换机制 简单粗暴：执行并发任务时，只需要把任务包装成一个函数，开启一个goroutine去执行函数即可，不需要自己去写进程、线程、协程。 使用goroutine 调用函数钱加上go关键字，即是为这个函数创建了一个goroutine 一个goroutine必定对应一个函数 可以创建多个goroutine去执行相同的函数 启动单个goroutine 1 2 3 4 5 6 7 8 func hello() { fmt.Println("Hello Goroutine!") } func main() { go hello() fmt.Println("Main Goroutine done!") } 只打印 Main Goroutine done!，为什么呢？ 程序启动时，Go程序会为main()函数创建一个默认的goroutine main()函数返回的时候，goroutine就结束了，所有在main()函数中启动的goroutine就一同结束 main()函数所在的goroutine就是 夜王，其余goroutine就是 异鬼，夜王一死，其余转化的异鬼一同GG 所以需要让main函数等待一下hello函数，简单粗暴的方法是time.sleep 1 2 3 4 5 func main() { go hello() // 启动另一个goroutine去执行hello函数 fmt.Println("Main Goroutine done!") time.Sleep(time.Second) } 先打印Main Goroutine done!，再打印Hello Goroutine! ...

九、反射 9.1 反射 9.1.1 变量的内在机制 Go语言中的变量分为两个部分 类型信息：预先定义好的元信息 值信息：运行过程中可动态变化 9.1.2 反射介绍 反射是指：在程序运行期对程序本身进行访问和修改的能力 程序在编译时，变量被转换为内存地址，变量名不会被编译器写入到可执行部分。在运行程序时，程序无法获取自身的信息。 支持反射的语言，可以在编译器将变量的反射信息，比如 字段名称、类型信息、结构体信息等 整合到可执行文件中，并给程序提供接口访问反射信息，这样就可以获取反射，并且有能力修改它们。 Go程序运行期间使用reflect包访问程序的反射信息 空接口可以存储任意类型的变量，反射就是在运行期间动态获取一个变量的类型信息和值信息 9.2 reflect包 接口值 = 一个具体类型 + 具体类型的值 接口值在反射中都由reflect.TypeOf和reflect.ValueOf两个函数来获取任意对象的Value和Type。 9.2.1 TypeOf 1 2 3 4 5 6 7 8 9 10 11 func reflectType(x interface{}) { v := reflect.TypeOf(x) fmt.Printf("type: %v\n", v) } func main() { var a float32 = 3.14 // type: float32 reflectType(a) var b int64 = 100 reflectType(b) // type: int64 } type name和type kind 类型还分为两种，类型（Type）和种类（Kind） 类型（Type）：person类型，struct种类 ...

八、包 Go语言的源码复用是建立在包（package）基础之上的 8.1 包介绍 包（package）是多个Go源码的集合，是一种高级的代码复用方案，Go语言为我们提供了很多内置包，如fmt、os、io等。 8.2 定义包 可以根据自己的需要创建自己的包，一个包可以理解为一个存放.go 文件的文件夹 所有.go文件都要在代码的第一行添加如下代码，声明该文件归属的包 1 package 包名 注意事项： 一个文件夹下面只能有一个包，同样一个包的文件不能在多个文件夹下。 包名可以不和文件夹的名字一样，包名不能包含-符号。 包名为main的包为应用程序的入口包，编译时不包含main包的源代码时不会得到可执行文件。 8.3 可见性 标识符（如变量、常量、类型、函数等）的首字母大写就可以让标识符对外可见了 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 package pkg2 import "fmt" // 首字母小写，外部包不可见 var a = 100 // 首字母大写，外部包可见 const Mode = 1 // 首字母小写，外部包不可见 type person struct { name string } // 首字母大写，外部包可见 func Add(x, y int) int { return x + y } func age() { // 函数局部变量，外部包不可见，只能在当前函数内使用 var Age = 18 fmt.Println(Age) } 结构体内的字段 ： 结构体首字母大写 + 字段名首字母大写 = 外部包可访问 接口内的方法： 接口名首字母大写 + 方法名首字母大写 = 外部包可访问 1 2 3 4 5 6 7 8 9 10 11 // 结构体名首字母大写 type Student struct { Name string //包外可访问 class string //包外不可访问 } // 接口名首字母大写 type Payer interface { init() //包内访问 Pay() //包外可访问 } 8.4 包的导入 例子： ...

LRU缓存机制 题目 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。 进阶: 你是否可以在 O(1) 时间复杂度内完成这两种操作？ 示例： 1 2 3 4 5 6 7 8 9 10 11 LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lru-cache 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ...

七、接口 接口（interface）定义了一个对象的行为规范，只定义规范不实现，由具体的对象来实现规范的细节。 接口类型 Go语言中的结口是一种抽象类型，是一组 method 的集合 定义一个协议（规则），不关心属性（数据），只关心行为（方法） 为什么要接口 比如一个网上商城可能使用支付宝、微信、银联等方式去在线支付，我们能不能把它们当成“支付方式”来处理呢？ 比如三角形，四边形，圆形都能计算周长和面积，我们能不能把它们当成“图形”来处理呢？ 比如销售、行政、程序员都能计算月薪，我们能不能把他们当成“员工”来处理呢？ 接口区别于我们之前所有的具体类型，接口是一种抽象的类型。当你看到一个接口类型的值时，你不知道它是什么，唯一知道的是通过它的方法能做什么。 接口的定义 每个接口由数个方法组成 1 2 3 4 5 6 7 8 type 接口名称 interface { 方法1( 参数列表1 ) 返回值列表1 方法2( 参数列表2 ) 返回值列表2 } type writer interface { Write([]byte) error } 接口名：使用type将接口定义为自定义的类型名。 接口命名时，一般会在单词后面添加er， 如有写操作的接口叫Writer，有字符串功能的接口叫Stringer等。 接口名最好要能突出该接口的类型含义。 方法名：当方法名首字母是大写且这个接口类型名首字母也是大写时，这个方法可以被接口所在的包（package）之外的代码访问。 参数列表、返回值列表：参数列表和返回值列表中的参数变量名可以省略。 实现接口的条件 对象只要全部实现接口内的方法，那么就实现了这个接口 接口即：需要实现方法的列表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 // 定一个 Sayer接口 type Sayer interface { say() } // 定义 dog 和 cat 两个结构体 type dog struct {} type cat struct {} // 给 dog 和 cat 分别实现 say 方法即实现了 Sayer 接口 func (d dog) say() { fmt.Println("汪汪汪") } func (c cat) say() { fmt.Println("喵喵喵") } 接口类型变量 1 2 3 4 5 6 7 8 9 func main() { var x Sayer // 声明一个Sayer类型的变量x a := cat{} // 实例化一个cat b := dog{} // 实例化一个dog x = a // 可以把cat实例直接赋值给x x.say() // 喵喵喵 x = b // 可以把dog实例直接赋值给x x.say() // 汪汪汪 } 值接收者和指针接收者实现接口的区别 以一个例子查看这其中的区别： ...

六、方法 方法是与 对象实例绑定 的特殊函数，是一个面向对象的概念 方法的函数定义语法的区别：方法有前置实力接收参数 构造函数 建议返回结构体指针类型（值拷贝开销较大） 1 2 3 4 5 6 7 func newPerson(name, city string, age int8) *Person { return &Person{ name: name, city: city, age: age, } } 调用构造函数 1 2 3 p := newPerson("Aris", "HB", 20) fmt.Printf("%#v\n", p) // &main.Person{name:"Aris", city:"HB", age:20} 方法 和 接受者 Go语言中的方法（Method）是一种作用于特定类型变量的函数。这种特定类型变量叫做接收者（Receiver）。 接收者的概念就类似于其他语言中的this或者 self。 1 2 3 func (接收者变量 接收者类型) 方法名(参数列表) (返回参数) { 函数体 } 接收者变量：接收者中的参数变量名在命名时，官方建议使用接收者类型名的第一个小写字母，而不是self、this之类的命名。 例如，Person类型的接收者变量应该命名为 p，Connector类型的接收者变量应该命名为c等。 接收者类型：接收者类型和参数类似，可以是指针类型和非指针类型。 方法名、参数列表、返回参数：具体格式与函数定义相同。 例子： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 func newPerson(name string, age int8) *Person { return &Person{ name: name, age: age, } } func (p Person) Dream() { fmt.Printf("%s的梦想是学好Go！\n", p.name) } func main() { p := newPerson("Aris", 20) p.Dream() // Aris的梦想是学好Go！ } 指针类型的接受者 用于修改实际的成员变量 ...

平衡二叉树 题目 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false 。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/balanced-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ...

验证二叉搜索树 题目 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 示例 1: 输入: 2 / \ 1 3 输出: true 示例 2: 输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/validate-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ...

在排序数组中查找元素的第一个和最后一个位置 题目 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 [-1, -1]。 示例 1: 1 2 输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4] 示例 2: 1 2 输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 直接二分法，找到pos位置 然后pos向左、向右遍历找到边界 解答 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 func searchRange(nums []int, target int) []int { if len(nums) == 0 { return []int{-1, -1} } low, high, pos := 0, len(nums)-1, 0 // 二分法 for low <= high { pos = low + (high-low)>>2 if nums[pos] == target { break } if target < nums[pos] { high = pos-1 } else { low = pos+1 } } if target != nums[pos] { return []int{-1, -1} } ret := []int{-1, -1} for i := pos; i >= 0; i-- { if nums[i] == target { ret[0] = i } else { break } } for i := pos; i < len(nums); i++ { if nums[i] == target { ret[1] = i } else { break } } return ret } // 执行用时 :8 ms, 在所有 Go 提交中击败了94.39%的用户 // 内存消耗 :4.1 MB, 在所有 Go 提交中击败了100.00%的用户

最大子序和 题目 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 1 2 3 4 5 6 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-subarray 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 遍历更新最大 动态规划，一维DP 遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 func maxSubArray(nums []int) int { if nums == nil || len(nums) == 0 { // errors.New("") return 0 } sum, max := nums[0], nums[0] for _, v := range nums[1:] { // 注意是从第二个元素开始遍历 if sum < 0 { sum = 0 } sum += v if max < sum { max = sum } } return max } // 执行用时 :8 ms, 在所有 Go 提交中击败了65.46%的用户 // 内存消耗 :3.3 MB, 在所有 Go 提交中击败了65.13%的用户 动态规划 问题拆分 ...

加一 题目 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以零开头。 1 2 3 4 5 6 7 8 9 示例 1: 输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。 示例 2: 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/plus-one 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 从最后一位做加法 要考虑为9加一进位的问题，以及最后超过数组长度的情况（9999） 0～8： 直接+1，然后break出循环 9：置0，继续往前 注意最后还要判断首位是否为0 解答 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 func plusOne(digits []int) []int { for i := len(digits)-1; i >= 0; i-- { if digits[i] != 9 { digits[i]++ break } digits[i] = 0 } if digits[0] == 0 { digits = append([]int{1}, digits...) } return digits } // 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户 // 内存消耗 :3.3 MB, 在所有 Go 提交中击败了97.77%的用户 收获 对于循环条件，每次进行len()操作，是否会拖慢计算：不存在， 长度len是slice本身的一个属性，获取其值就是访问变量，没必要再创建一个变量才存储这个值（针对本题的场景） ...

K 个一组翻转链表 题目 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 1 2 3 4 示例： 给你这个链表：1->2->3->4->5 当 k = 2 时，应当返回: 2->1->4->3->5 当 k = 3 时，应当返回: 3->2->1->4->5 说明： 你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 开创一个新链表来存储反转后的思路行不通，因为规定时间复杂度是常数级的 尾插法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 dummy 1 2 3 4 5 pre head tail # 用tail前进K个位置 dummy 1 2 3 4 5 pre head tail cur # 尾插法：依次把cur移到tail后面 dummy 2 3 1 4 5 pre cur tail head # go on dummy 3 2 1 4 5 pre tail head cur .... 解答 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 type ListNode struct { Val int Next *ListNode } func reverseKGroup(head *ListNode, k int) *ListNode { if k <= 1 || head == nil { return head } dummy := &ListNode{} dummy.Next = head pre, tail := dummy, dummy for { // 1. tail 前进k个位置 var count int for count != k && tail != nil { tail = tail.Next count++ } if tail == nil { // 抵达尾部 break } // 2. 尾插 tmp := pre.Next // 暂存第一个 for pre.Next != tail { cur := pre.Next pre.Next = cur.Next cur.Next = tail.Next tail.Next = cur } pre, tail = tmp, tmp } return dummy.Next } // 执行用时 :8 ms, 在所有 Go 提交中击败了15.08%的用户 // 内存消耗 :3.6 MB, 在所有 Go 提交中击败了100.00%的用户 其它解 临时栈，入栈出栈拼接 递归 优化 无 ...

合并两个有序链表 题目 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 1 2 3 4 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 新建一个结点，遍历两个链表，取小的往新结点上接 被取到的链表往前遍历 新链表创建一个头节点指针，把这个指针赋值给游标结点 游标结点往前走，接收接上来的结点 最后结果为头节点的Next 解答 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 type ListNode struct { Val int Next *ListNode } func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { pre := &ListNode{} cursor := pre for l1 != nil && l2 != nil { if l1.Val > l2.Val { cursor.Next = l2 l2 = l2.Next } else { cursor.Next = l1 l1 = l1.Next } cursor = cursor.Next // 游标结点也要前进 } if l1 != nil { cursor.Next = l1 } else { cursor.Next = l2 } return pre.Next } // 执行用时 :4 ms, 在所有 Go 提交中击败了67.48%的用户 // 内存消耗 :2.5 MB, 在所有 Go 提交中击败了86.48%的用户 优化 无 ...

有效的括号 题目 给定一个只包括 (，)，{，}，[，] 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 示例 1: 输入: "()" 输出: true 示例 2: 输入: "()[]{}" 输出: true 示例 3: 输入: "(]" 输出: false 示例 4: 输入: "([)]" 输出: false 示例 5: 输入: "{[]}" 输出: true 来源：力扣（LeetCode） ...

两数之和 题目 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 1 2 3 4 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 解答 解答一 暴力 复杂度为O(n2) 高低指针：低指针从前到后，高指针从低指针开始向后，遇到符合条件的退出 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 func twoSum(nums []int, target int) []int { if len(nums) == 0 { return []int{} } for k1, v1 := range nums { for k2, v2 := range nums[k1+1:] { if v1+v2 == target { return []int{k1, k1 + 1 + k2} } } } return []int{} } // 执行用时 :64 ms, 在所有 Go 提交中击败了38.45%的用户 // 内存消耗 :2.9 MB, 在所有 Go 提交中击败了100.00%的用户 解法二 遍历: O(n) ...

五、数据 5.1 字符串 默认值为 ""而不是nil 换行字符串使用 `，前置缩进空格也属于字符串内容 1 2 3 4 5 6 7 8 func main() { s := `line\r\n, line 2` fmt.Println(s) } // 输出： // line\r\n, // line 2 支持字符串间的比较 允许以索引号访问字节数组，但不能获取元素地址 分配超大字符串 ==92== 5.2 数组 定义方式： 1 2 3 4 5 6 7 8 9 10 11 12 13 func main() { var a [4]int b := [4]int{2, 5} // 未初始化的元素默认为0 c := [4]int{5, 3: 10} // 指定索引位置初始化 d := [...]int{1, 2, 3} // 编辑器按照初始化值数量确定数组长度 e := [...]int{10, 3: 100} // e 长度为 4，因为设定了索引位置 fmt.Println(a, b, c, d, e, len(e)) } 元素类型相同，长度也相同时才属于同一类型，才能直接赋值 ...

三数之和 题目 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 1 2 3 4 5 6 7 8 9 示例： 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/3sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 借用二元组，a = -(b+c) 即：遍历数组，从后面的集合里面找到两个数加起来是它的相反数，复杂度为O(n2) 注意剪枝和去重复 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 func threeSum(nums []int) [][]int { if nums == nil || len(nums) < 3 { return nil } sort.Ints(nums) var ret [][]int for k, v := range nums { // 剪枝：排序后第一个字不可能大于0 || 后面还剩下一个数字 if v > 0 || len(nums)-1-k <= 1 { break } if k > 0 && v == nums[k-1] { // 去重复 continue } // 后面的集合里面找 tmp := twoSUm(nums[k+1:], -v) if tmp != nil { for _, t := range tmp { // 先把满足条件的v塞入二元组，再把二元组塞入三元组 ret = append(ret, append(t, v)) } } } return ret } //求所有满足情况的二元组 func twoSUm(nums []int, target int) (ret [][]int) { var ( m = make(map[int]bool, len(nums)) record = make(map[int]bool, len(nums)) ) for _, v := range nums { dif := target - v // map内包含符合条件的 target-v && 去重复([1,2] [2,1]) if m[dif] && !record[v] { ret = append(ret, []int{v, dif}) record[v] = true //标记重复 } else { m[v] = true // 标记暂不符合条件的值 } } return }

四、函数 4.1 定义 使用 func 定义函数，特性如下： 无须前置声明 不支持同名函数重载 不支持命名嵌套 nested – ？ 不支持默认参数 不支持定长变参 ==支持多返回值== 支持命名返回值 支持匿名函数和闭包 函数属于第一类对象，具备相同签名（参数和返回值一样）的视为同一类型 第一类对象：可在运行期创建，可作函数参数或返回值，可存入变量的实体。最常见的就是匿名函数 1 2 3 4 5 6 7 8 9 10 11 12 13 func hello() { fmt.Println("hello world!") } // exec函数，参数值为函数名称 func exec(f func()) { f() } func main(){ f := hello exec(f) } 函数只能判断是否 ==nil，其余操作不支持 建议命名 动词介词加名词 scanWords 避免不必要的缩写 printError优于 printErr 避免使用类型关键字 buildUserStruct看上去很别扭 避免歧义 避免只能通过大小写来区分的同名函数 避免使用内置函数名 避免使用数字，除非是UTF8这种专有名词 避免添加作用域提示前缀 统一使用 camel/pascal case 拼写风格 （驼峰） 使用相同术语保持一致性 使用习惯语，比如 init初始化，is/has 返回布尔值 使用反义词组命名行为相反的函数，get/set、min/max 4.2 参数 形参：函数定义中的参数 类似局部变量 实参：函数调用时所传递的参数 函数外部对象，可以是常量、变量、表达式或函数等 ==Golang是值传递==，也称作拷贝传递（pass-by-value），函数调用前，会为形参和返回值分配内存空间，并将实参拷贝到形参内存 ...