今日提交三个算法题：两数之和、两数相加和最长无重复字符子串。
一、两数之和
难度：简单
题目传送门：两数之和
题目
给定一个整数数组 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]
提示：
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- 只会存在一个有效答案
思路
将number放到map中，然后遍历数组，找target-数组元素是否存在于map中。命中条件：存在，且下标不相同。
代码
func twoSum(nums []int, target int) []int {
m := make(map[int][]int, len(nums))
for i, n := range nums {
if a, ok := m[n]; ok {
m[n] = append(a, i)
} else {
m[n] = []int{i}
}
}
for i, n1 := range nums {
if js, exist := m[target-n1]; exist {
for _, j := range js {
if j == i {
continue
}
return []int{i, j}
}
}
}
return nil
}
二、两数相加
难度：中等
题目传送门：两数相加
题目
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字0之外，这两个数都不会以0开头。
提示：
- 每个链表中的节点数在范围 [1, 100] 内
- 0 <= Node.val <= 9
- 题目数据保证列表表示的数字不含前导零
思路
对应位置相加，进位保留在nextNode中，结束条件为：进位为0，且两个列表均遍历完成。
代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
nextA, nextB := l1, l2
nextNode := new(ListNode)
begin := nextNode
for {
var a, b int
if nextA != nil {
a = nextA.Val
nextA = nextA.Next
}
if nextB != nil {
b = nextB.Val
nextB = nextB.Next
}
preVal := nextNode.Val
nextNode.Val = (preVal + a + b) % 10
next := new(ListNode)
next.Val = (preVal + a + b) / 10
if nextA == nil && nextB == nil && next.Val == 0 {
break
}
nextNode.Next = next
nextNode = next
}
return begin
}
三、无重复字符的最长子串
难度：中等
题目传送门：无重复字符的最长子串
题目
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
提示：
- 0 <= s.length <= 5 * 104
- s 由英文字母、数字、符号和空格组成
思路
设置滑动窗口，窗口为不重复的子串。每个子串需要计算最大长度，选最大的保留下来。
代码
func lengthOfLongestSubstring(s string) int {
if s == "" {
return 0
}
// 用来存储字符的unicode编码对应的最新出现的位置
// 128仅能存放size为一个字节的字符，如果超过，则需要设置更大一些
last := make([]int, 128)
for i := range last {
last[i] = -1
}
max, start := 0, 0
for i := 0;i<len(s);i++ {
r := s[i]
if last[r] > -1 {
// 字符在前面出现过
if last[r]+1 > start {
start = last[r] + 1
}
}
if i-start+1 > max {
max = i - start + 1
}
last[r] = i
}
return max
}
感想
这个题做了50分钟，提交第一次正确答案花费了20分钟，成绩为：156ms 6.7MB.
| 序号 | 执行用时(ms) | 内存消耗(MB) | 提交时间 |
|---|---|---|---|
| 1 | 156 | 6.7 | 23:23 |
| 2 | 20 | 6 | 23:37 |
| 3 | 4 | 2.7 | 23:53 |
| 4 | <1 | 2.3 | 23:55 |
最开始的想法是：使用哈希表来存储字串的子符，每次需要重新计算子串时，循环清空哈希表。这样导致多次多处循环，且内存消耗大。
后续改变思路，通过unicode编码在数组中的映射，直接记录字符出现的位置，避免用哈希表等存储临时字符串的的问题。极大的优化了CPU和内存消耗。