LeetCode-两数之和

来年就要找工作了，刷刷lc复习数据结构和算法。两数之和是第一道题，可能也是最简单的一道题，我准备从这里开始记录我的思路。

读过面经的同学可能会经常看到有大佬说：

就算是白板写代码，除了Coding能力之外最重要的就是要会沟通，首要要问清需求，不要盲目开始写代码，然后思考理清思路，与面试官交流一番，获得认可之后再开始写代码，这个过程中如果没有思路，也可以和面试官商讨，并且与其讨论优化方案。

所以我的想法在复习过程中尽可能的从暴力解法开始优化思路。

正文

两数之和

1. 最brute的思路：双层循环遍历数组，最容易想到并且实现起来简单，时间复杂度是O(n²)，这种面试官肯定会让我们继续给出优化的方法。
2. 遍历时需要执行很多次加法，考虑到和target已给出，第一层循环得到加数一num1，那么加数二num2可以由target-num1得出，只需要比较当前值是否等于num2，当然这里提升太小了。注意命名最好让人一眼看出作用
3. 如果数组是有序的，就简单多了，从数组小的一端取num1，由target-num1得出num2，然后从数组另一端开始判断，如果最大的数小于num2那么无解，否则一直搜索到小于等于num2的值，如果等于num2，则可以满足条件，下一步找出原来的下标。排序用快排好了。注意边界条件
4. 排序+双指针，num1从小端往大端，num2从大端到小端，如果num1+num2小于target，那么num1移动一位，如果大于则num2移动一位，直到相等则满足条件，计算原来下标，或者num1和num2相遇，没有结果。双指针只需要O（n)，时间主要花在排序上，所以时间复杂度是O(nlogn)。
5. 最简单最快的哈希法，遍历过程中，计算sum-num1检查得到的num2是否在哈希表中，如果不在，将num1加入哈希表，如果在输出num2和num1的下标即可。哈希是O(n)，遍历也是O(n)，所以，时间复杂度是O(n)。

LeetCode不是写完整代码，手撕代码是否需要写出完整代码，包括头文件？有些公司还需要自己写测试案例，各种边界要考虑全面，也别忘了验证程序正确的案例。