_(:з」∠)_ 因为实在是太久没有写文章但是又找不到有什么东西好写的，正好最近被某 Tyanboot 带入了 LeetCode 刷题的坑，所以想了想，索性就开了这个帖子记录一下在 LeetCode 的刷题历程好了。因为不想用一题一篇文章的记录方式，所以就直接扔在一整篇博文里。因为时间比较少（被续掉的（不是））所以大概就是 1~2 周做一题、更一题的样子。当然遇到更难的题目另外说……

（题外：西方的 LeetCode 比什么 *gu 一类的 Online Judge 不知道高到哪里去了！）

目录 (Content)

[Problem 1] Two sum 简单的两数求和（斜眼笑） [Problem 2] Add Two Numbers 真 · 两数求和 [Problem 3] Longest Substring Without Repeating Characters 找到一串字符串最长不重复的子串

[Problem 1] Two sum

一开始看难度 Easy，以为又是普通 OJ 的那种 A+B 问题，点进去一看才发现……我毕竟还是图样图森破啊。 呐。问题的大意就是给你一个不定长的整数数组 nums，里面的数不会重复；再给你一个目标数 target，然后让你求出数组中的哪两个数加起来等于目标数。 （喂，这和我们说好的水题不一样啊！） 其实还是可以的啦，题目给的标签是哈希表，那就照着这个方向写吧。这里哈希表用STL 的 map 来建好了，也是很方便的（问题是写这题之前还没试过用 map 呢 orz） 代码 Gist 地址：https://gist.github.com/kirainmoe/919ee87b7653ada8689fbe2384503bd5#file-two_sum-cpp 做题的时候参考的： 《C++ 中的 STL 中 map 用法详解》：http://blog.sina.com.cn/s/blog_a9303fd9010195hm.html

---

[Problem 2] Add Two Numbers

稍有常识的人就能看出，如果我们的铁骑继续前进 这道题目就是一个高精度加法运算的链表实现形式： Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 把高精度的模板套过来使之与链表相适即可。但是受 Top solution 的一个题解的启发，原来代码可以写得更简洁，如下，代码不长不扔 Gist 了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode a = ListNode(0), *ans = &a;
        int remain = 0;         // 剩余
    // l1, l2 都为空之后，切记要处理最后剩余的
    while (l1 != NULL || l2 != NULL || remain != 0)
        {
            int cur = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + remain;
            remain = cur / 10;
            ans->next = new ListNode(cur % 10);
            ans = ans->next;
            
            // 下一位，记得判断一下 l1, l2 的 next 是否为 NULL
            l1 = l1 ? l1->next : l1;
            l2 = l2 ? l2->next : l2;
        }
        
        return a.next;
    }
};

就是这样的喵。

---

[Problem 3] Longest Substring Without Repeating Characters

其实做这道题目距离今天已经有一段日子了……也是我 LeetCode 的入坑题。难度是 Medium ，但是我觉得这个比上一题简单的说。

题目大意是给你一个字符串，找出最长的不重复子串，然后返回这个不重复子串的长度。比如说：

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

刚看到这道题目的时候，想到以前好像做过类似的题目可以用 DP 来求解，仔细想想发现不需要用动态规划，并且可以把时间复杂度控制在 O(n)。具体的做法如下：

首先维护一个长度为 96 的数组 pos，因为这里题目给出来的字符串不只包括大小写字母，还包括特殊符号（喂，不带不给数据范围的啊），但是都在 ASCII 能表示的范围内，用这个数组作为 Flag。用 memset() 把这个数组赋上初值 -1。定义一个叫 ans 和 cur 的整形变量，分别用来存储最终答案和当前搜到的最长不重复子串的长度，初值都让他们为 0。最后我们还需要一个作为指针作用的变量 flag = s.length().

接下来就是求解。将这个字符串从后往前搜（length-1→0），定义一个叫做 tmp 的变量保存当前遍历到的字符的 ASCII 码与 32 的差（s[i]-32，这里与 32 做差的原因是我们上文只定义了 96 的数组长度）。接着对 pos[tmp] 做判断： 如果 pos[tmp] == -1，说明到目前为止还没有遇到过这个字母，那么令 cur += 1，接着判断 cur 和 ans 的关系，如果 cur > ans，就用 cur 的值替换 ans 的值。

如果 pos[tmp] != -1，说明在之前已经遇到了这个字母，而现在又遇到了，这个时候需要判断 pos[tmp] 和 flag 的大小关系。

== 如果 pos[tmp] > flag，这个时候说明 flag 在当前搜到的字符(tmp) 上一次出现之后已经更新过了，那么这时候我们就令 cur = flag-i（这个时候，从 i 到 flag 的字符共同组成从 s[i] 开始往下能取到的最长不重复子串），然后比较 ans 和 cur，更新 ans 的值。

== 如果 pos[tmp] < flag，那么更新 flag 的值，让 flag = pos[tmp]（这么做的原因是因为如果 pos[tmp] 在 flag 之前，那么从 i 开始能取到的最长不重复子串就会变成 i 到 pos[tmp]-1之间的所有字符）。这个时候就可以令 cur = flag-i 了。由于这个时候得到的新值必定比 ans 小，所以就不需要做比较了。

做完这一切还有最后一件事，就是更新当前字母出现的位置啦。别忘记在循环体最后加上 pos[tmp] = i 更新一下位置。最后就大胆地 return ans; 吧。

代码 Gist 地址：https://gist.github.com/kirainmoe/a39a65e73efc95012bb7be84d32337c7 由于理想情况下复杂度是 O(n) ，所以实测最快可以在 LeetCode 跑到 9ms 左右（这个成绩是超过 99.57% 的提交）