没事的时候打算开始玩一玩leetcode，不然天天写代码，却对算法没啥认识还是有点尴尬的。虽说是做题，其实大部分就是为了看看别人牛逼的思路。尽量每天一题把～

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。例： 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

第一种方法就是便利数组，随着数组长度增加，执行时间指数型增加。

#时间复杂度：O(n^2)#空间复杂度：O(1)func twoSum(nums []int, target int) []int { for firstIndex,firstNum := range nums{ for secondIndex,secondNum := range nums{ if firstIndex != secondIndex && firstNum + secondNum == target{ return []int{firstIndex, secondIndex} } } } return nil}

第二种方式是以空间换时间，把数据存在哈希表里面，最多只用完全遍历一次数组，就能得到结果。

#时间复杂度：O(n)#空间复杂度：O(n)func twoSumHash(nums []int, target int) []int { m := make(map[int]int) for index,num := range nums{ i,ok := m[target - num] if ok { return []int{i,index} } m[num] = index } return nil}

题目链接：https://leetcode-cn.com/problems/two-sum/description/

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8 原因：342 + 465 = 807

这个题主要有两个地方卡了我一下，第一，输入的两个链表可能是不一样长的，第二，最后一位相加可能会进1，所以此时，输出比输入多一位数字，就是多一个节点。
我在思考次题目时候，想方设法的想把输出链表的第一个节点，填入数字，其实可以这样。链表第一个节点可以为空，然后从第二个节点赋值，最后return时候，返回head.Next。咳咳，早已忘记当年学数据结构的时候，就是这么干的。
我的答案：

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { l := new(ListNode) temp := l lsum := 0 for { if l1 != nil{ lsum += l1.Val l1 = l1.Next } if l2 != nil{ lsum += l2.Val l2 = l2.Next } temp.Val = lsum % 10 lsum = lsum / 10 if lsum != 0 || l1 != nil || l2 != nil{ nextNode := new(ListNode) temp.Next = nextNode temp = temp.Next }else{ break } } return l}

网站给出的答案：

func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode{ dummyHead := new(ListNode) p,q,curr := l1,l2,dummyHead carry := 0 for p !=nil || q != nil{ x,y := 0,0 if p != nil { x = p.Val } if q != nil { y = q.Val } sum := x + y + carry carry = sum /10 curr.Next = new(ListNode) curr = curr.Next curr.Val = sum % 10 if p !=nil{ p = p.Next } if q !=nil{ q = q.Next } } if carry > 0{ curr.Next = &ListNode{Val:carry} } return dummyHead.Next}

网站的答案会把l1和l2赋值给一个临时变量，这样就不会影响函数外的l1，l2，这是我所忽略的。
网站的答案，把sum和carry分成两个变量，增强了可读性，我放在一起，基本上就看不出来为啥，除以10赋值给sum。然后我变量命名过于随意。

看见字符串匹配的题的就怂，所以卡了好几天不敢做。我自己的答案倒是尝试快10次了。才通过所有的测试。坑的点还是不少的。说下我的实现思路吧。

func lengthOfLongestSubstring(s string) int { filter := make(map[int32]int) // 比较喜欢用哈希表统计重复 lastKey := 0 // 记录重复时，与本次重复的上一次重复点的下一位的index（非重复开始的位置） //比如当前字母的index为10，与之重复的字母的index为5，那么lastKey的值就赋值为5 max := 0 //最大连续不重复字串的长度 for k,v := range s{ //遍历字串 index,ok := filter[v] //判断是否发生重复 if ok { //发生重复 if k - lastKey >max{ //计算重复点到上一个重复点的长度 max = k - lastKey } for i := lastKey;i<index;i++{ //index是与当前字母重复的所在位置，删除此位置之前的所有字母。 delete(filter, int32(s[i])) } lastKey = index+1 } filter[v] = k //新增或更新当前字母的index值 } if len(s) - lastKey > max{ //有可能中间某个点，到最后一个字母都没有重复，所以不会触发ok里面的检测，因此判断非重复点到最后一个字母的距离。 max = len(s) - lastKey } return max}

网站给的答案：

# i和j就是字串的开始坐标和结束坐标。遍历字符串s，如果当前字母，在字串i，j中没有重复，则j加1，即字串长度加一，如果当前字母在i，j中有重复的，则删除字串的第一个字母。因为有可能重复的字母在i，j中间，所以就会一直删除字串的第一个字母，直到删除至子串中没有重复的字母。就得到了，非重复字串。#思路是真的好呀。之前我一直纠结怎么，当字串中有重复字母的时候，怎么确定，map中删除哪些key，网站的思路就很流畅呀！！！赞！func lengthOfLongestSubstring(s string) int { filter := make(map[uint8]int) n := len(s) i,j,max := 0,0,0 for i < n && j < n { _,ok := filter[s[j]] if !ok{ filter[s[j]] = 0 j++ if j - i > max{ max = j - i } }else { delete(filter,s[i]) i++ } } return max}2.优化的滑动窗口,原来网站也有map的思路

#其实放入map中的值并不需要删除....对比一下，我写的答案太low了。。。func lengthOfLongestSubstring(s string) int { filter := make(map[uint8]int) n := len(s) max := 0 for i,j := 0,0; j < n; j++ { index,ok := filter[s[j]] #判断当前字母是否在map中已存在 if ok{ #如果存在，就把index赋值给i if index > i { #比如map中有一个字母a，他的index为3,如果当前字母也为a，就吧之前a的index保存到i中 i = index #为什么判断大小呢？假如a的index为3，他前面有一个字母b，当前字母为a，所以i为3，如果下一个字母为b，因为上一个a之前有一个b，所以b是存在的，但是上一个b的在字母a前面，所以i不变。这就是map不用删除key的原因 } } if j - i +1 > max{ max = j - i + 1 } filter[s[j]] = j+1 } return max}4. 两个排序数组的中位数

题目：给两个有序的数组，取两个长度为n,m的数组的中位数，并且时间复杂度为Olog(min(n,m))
例1：

nums1 = [1, 3]nums2 = [2]中位数是 2.0

例2:

nums1 = [1, 2]nums2 = [3, 4]中位数是 (2 + 3)/2 = 2.5

其实这道题考的排序算法，所以哪个排序算法的时间复杂度是O(log n)呢，还给了两个有序的数组，第一想到的就是归并排序的最后一步。

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { i,j := 0,0 sorted := make([]int,0) for i < len(nums1) && j < len(nums2){ if nums1[i] > nums2[j]{ sorted = append(sorted,nums2[j]) j++ }else { sorted = append(sorted,nums1[i]) i++ } } sorted = append(sorted,nums1[i:]...) sorted = append(sorted,nums2[j:]...) n := len(sorted) if n % 2 ==0{ return (float64(sorted[n/2-1]) + float64(sorted[n/2]))/2 } return float64(sorted[(n-1)/2])}

嘤嘤嘤，网站答案看的脑壳疼。。。。
看完网站的答案，我掐指一算，我的时间复杂度是O(min(n,m)),想要时间复杂度为O(log(mint(n,m))),就得用二分法。分析过程好复杂，脑壳疼。实现也复杂，要考虑的因素好多。。。。