LeetCode刷题笔记（1）

一个人的命运啊，不仅要考虑历史的进程，还要考虑个人的努力，近期明显懈怠下来的笔者决定开启LeetCode刷题大业，从第一题开始按顺序刷掉LeetCode算法题，把解题的笔记放在这里，希望跟各位读者多多交流。

编程语言，话不多说，即刻开始：

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

这道题目要求找出一个List中的两个数，使得他们的和等于给定的，然后返回这两个数在List中的位置，笔者第一时间的想法便是遍历整个List，对每一个小于的数，看List中是否有这个数，再返回他们的位置，也就是下面的解法2，解法3是解法2更Pythonic的形式，由于列表查找的时间复杂度是O(n)，所以整个算法的时间复杂度是O(n^2)。

那么如果想要增加效率，可以将列表查找转换为hash table也就是Python里的Dict对象，也就是下文中的解法1，因为hash table的查找速度近乎于O(1)，所以整个算法的时间复杂度是O(n)。

2. Add two numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

这道题目要求我们实现整数的加法，这跟计算机ALU中加法器的原理是类似的，每一位加完之后会得到该位的结果和一个进位，进位的值只能取1或0。这里用到Python自带的一个很方便的函数可以返回两数相除的商和余数，商为进位，余数则为该位剩下的值。

值得注意的是，由于每个ListNode对象是单向传递的，所以需要在一开始保留一个根部的指针指向和的末位，计算完成后返回这个根部的指针。

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

算法题里面的一大类就是各种字符串操作题，本题要求找出最小不重复子字符串的长度，所以用变量储存当前找到的字符串，如果找到更长的，再加以替换，直到遍历完毕。

本题还有一种思路，因为题目只要求长度，所以可以只找位置之间的差别，不用存储子字符串，实现方法与上面类似。

第一次刷题，先放三道，欢迎大家交流讨论指正，有想一起刷题的同志可以私信我~