华为算法题 go语言

1

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

package mainimport "fmt"func twoSum(nums []int, target int) []int {numMap := make(map[int]int) // 前一个是键，后一个int是值，map是映射// 遍历数组 nums，i 是当前元素的索引，num 是当前元素的值for i, num := range nums {complement := target - num// j：这是从 numMap 中获取的与 complement 对应的值if j, ok := numMap[complement]; ok {// []int{j, i} 是一个整数切片的初始化.返回一个包含两个整数的切片，第一个整数是 j，第二个整数是 ireturn []int{j, i}}numMap[num] = i}return nil
}func main() {nums1 := []int{2, 7, 11, 15}target1 := 9result1 := twoSum(nums1, target1)fmt.Println(result1)nums2 := []int{3, 2, 4}target2 := 6result2 := twoSum(nums2, target2)fmt.Println(result2)
}

2

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
在这里插入图片描述

package mainimport "fmt"// 表示链表节点的数据结构
type ListNode struct {Val  intNext *ListNode
}// 接受两个非空链表，表示两个非负整数，返回它们的和的链表
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {// create 一个虚拟头节点dummyHead := &ListNode{}// create 一个指针current := dummyHead// 进位标志carry := 0// 遍历两个链表，直到两个链表都遍历完并且没有进位为止for l1 != nil || l2 != nil || carry > 0 {// 计算当前位的数字总和sum := carryif l1 != nil {sum += l1.Vall1 = l1.Next}if l2 != nil {sum += l2.Vall2 = l2.Next}// 更新进位  ,注意这里如果小于10carry就是0，否则为1carry = sum / 10// 创建新节点存储当前位的数字current.Next = &ListNode{Val: sum % 10}// 将指针移动到下一个节点current = current.Next}// 返回结果链表的头节点的下一个节点（跳过虚拟头节点）return dummyHead.Next
}// 用于打印链表的值，方便查看结果
func printLinkedList(node *ListNode) {for node != nil {fmt.Print(node.Val)if node.Next != nil {fmt.Print("->")}node = node.Next}fmt.Println()
}func main() {// 实例1l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3}}}l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4}}}result := addTwoNumbers(l1, l2)printLinkedList(result)
}

3

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

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

假设我们有一个字符串：s = "abcabcbb"。

我们开始遍历这个字符串，使用一个“盒子”来存储不重复的字符。

我们从字符串的开头开始，第一个字符是 ‘a’，我们放入盒子中，盒子内有：[a]，目前盒子的长度为1。
接着是 ‘b’，我们放入盒子中，盒子内有：[a, b]，目前盒子的长度为2。
然后是 ‘c’，我们放入盒子中，盒子内有：[a, b, c]，目前盒子的长度为3。
然后又是 ‘a’，在这里我们发现盒子内已经有了 ‘a’，所以我们需要重新开始计算盒子。我们将 ‘a’ 上一次出现的位置后面的字符都去掉，得到新的盒子内容为 [b, c, a]，目前盒子的长度为3。
然后是 ‘b’，我们放入盒子中，盒子内有：[b, c, a]，目前盒子的长度为3。
接着是 ‘c’，我们发现 ‘c’ 已经在盒子中了，所以我们需要重新开始计算盒子。我们将 ‘c’ 上一次出现的位置后面的字符都去掉，得到新的盒子内容为 [a, b, c]，目前盒子的长度为3。
最后是 ‘b’，我们放入盒子中，盒子内有：[a, b, c]，目前盒子的长度为3。

我们遍历完整个字符串后，最长的不含重复字符的子串就是 “abc”，它的长度为 3。

package mainimport "fmt"
// start 和 i 分别表示当前不含重复字符的子串的起始位置和结束位置。lastI 表示字符上一次出现的位置。func lengthOfLongestSubstring(s string) int {// 使用 map 存储字符最后出现的位置lastOccurred := make(map[byte]int)start, maxLength := 0, 0// 遍历字符串for i, ch := range []byte(s) {// 如果字符已经出现过，并且出现位置在当前子串中if lastI, ok := lastOccurred[ch]; ok && lastI >= start {start = lastI + 1 // 更新子串起始位置}// 更新字符最后出现的位置lastOccurred[ch] = i// 更新最大子串长度if i-start+1 > maxLength {maxLength = i - start + 1}}return maxLength
}func main() {s1 := "abcabcbb"fmt.Println(lengthOfLongestSubstring(s1))
}