LeetCode560毫无新意 新手学习导论

上次发帖说是菜鸡，被提了意见。其实主要目的还是让人知道这不是专家贴，而是给刷题没上道的同学来借鉴参考的，让后来的同学可以少走一些弯路。顺便我把自己的思路总结一下，自己复习起来会方便很多。能把题讲出来，说明才是真的理解。（费曼学习法）

言归正传，我们看560 这道题。
题意：给一个array 看有多少个连续的数的和 等于 target k
input： int[] nums,  int k (target)
output: int (有多少种可能）

思路: 这道题乍一看非常像是，dfs的题目，尤其是如果你最近一直在刷dfs dp 或者bfs的题目的时候很容易就联想到了，用一个recursion来做回溯找到所有target等于k的组合。类似于subset sum 和 permutation 这一类的题目。
但很快，当你花费了7分钟左右写完所有逻辑进行测试的时候你惊讶的发现了题目中的一个条件。连续的subarray之和。显然回溯法很难实现这一个苛刻的条件。那么没经验的小伙伴能怎么办？作为新时代的猛人，我们当然是暴力解法。回忆一下你初高中的考试，每次当你考试，尤其是数学考试，面对大题，即使你不回，你不也得给那一页纸写满，老师至少会给你个辛苦分得。（也有人可能说，啊？数学考试还能有题你能不会写？我只能说是啊，我每次考完都会惊讶，我居然有题会写！）

那这道题的暴力解法是什么样的那？
testcase 【1,1,1】 k = 2
1. 第一个for loop i 从头跑到尾
2. 第二个for loop j 从i 从i跑到尾 （因为必须是连续的，所以一定是个从左向右的一个 区间 移动顺序）
3. 设置curSum += num[j] 当curSum 等于k的时候 我们 res += 1。
注意一点的是，当时我写的时候在 curSum = k的时候 res += 1之后 加了个break 因为我觉得判断完了 但是会出现一个特殊情况 { array[-1, 1, 0] k = 0} 所以不能停下来

代码如下
class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            int sum = 0;
            for(int j = i; j < nums.length; j++){
                sum += nums[j];
                if(sum == k){
                    count += 1;
                }
            }
        }
        return count;
    }
}

这时候发现，人间奇迹，居然过了。 看了一眼 范围 1 - 20000 这个范围内 n^2 的时间是可以跑过test case 大概用时1300ms （花花酱说的，可以去翻翻他的视频）

Time o（n^2）
space o(1)
(Time limit 的暴力解法，我说实话，我没想到那么写，我还得琢磨半天才明白，这里就不赘述了可以去leetcode官方答案去看一下）

下一步，如果是面试的话，毕竟是个mid题，大概率他的follow up 会是让你优化，这也就是你们两个人互相表演的精髓所在，你得给他留台词，你得让他也参与到这场戏中，你别上来丢一个最优解，他都没法演了！

新手没有经验的人，会挠挠头，比如说我就是这样。这尼玛都能submit了 我还优化个蛋！这不是难为人吗？这时候就去看related topics。看看这道题和什么topic对应。

Prefix Sum.
看到是一脸的懵，那就找一个高票答案看一看把，用的hashmap 来回减来减去的。能打弹幕的话，我估计也是一屏幕的问号。这也就是我上一个帖子所说的，有的时候单纯看高票答案会陷入写完，背过，忘记，复习，再看跟新题一样，在背，在忘的一种循环之中，而且面试的时候，你啪一下咣咣敲键盘给他写完最优解，你要是不理解，他三两下就给你问si了。他不是考谁的硬盘大那，他是考我们的逻辑推理能力。

所以我们首先要弄明白什么是prefix sum （有兴趣小伙伴可以看一下这个youtube 视频 ——> 传送门 https://www.youtube.com/watch?v=7pJo_rM0z_s ）
总结一下视频内容 照猫画虎的说

我们有一个 Array[0, 1, 2, 3, 4], 当我们想要计算从index【0】至 index【2】和的时候
1. 暴力解法  index[0] + index[1] + index[2] = 3
那么学习过OOP的知识的同学很快就发现，暴力解法有一个问题，复用性太差，例如我们现在要计算index【0】到 index【3】的和的时候我们还是要从头算到尾
index[0] + index[1] + index[2] + index[3]= 6
显然这种蠢方法是真的没办法接受，这时候如果你在看视频，估计急的跳脚，你直接把 算好的和 放到对应的index里不就好了  

叮叮叮！！ 这就是prefix sum的精髓所在。

那么回到这道题我们尝试用prefix sum来解决这道题，

还是先从简单入手
思路
1. 先创建一个数组，专门存放所有计算prefix sum的element 我们叫他sumArr
2. 创建一个int res 来存放我们最终的结果
3. 第一个for loop i 从 头跑到sumArr 尾
4. 第二个for loop j 从 头跑到 i 截止
    a. 当sumArr中 sumArr[i] - sumArr[j] == k 的时候我们res += 1
但是！！！ 我们发现一个问题， test case 【1,2,3】 k = 3 的时候，我们的res 只存了1 应该是2 为啥那。因为 我们sumArr是【1,3,6】 相当于我们的逻辑至计算了6 - 3 = 3 这个情况，而没有计算 3 这个情况。
一拍脑子，想到了 我们把 sumArr 的长度扩充1格，设置一个 base case sumArr[0] = 0 不就好了，3-0 = 3； 6 - 3 = 3

思路重构
. 先创建一个数组，专门存放所有计算prefix sum的element 我们叫他sumArr 数组的长度是 原先array + 1 同时 设置base case sumArr[0] = 0
2. 创建一个int res 来存放我们最终的结果
3. 第一个for loop i 从 头跑到sumArr 尾
4. 第二个for loop j 从 头跑到 i 截止
    a. 当sumArr中 sumArr[i] - sumArr[j] == k 的时候我们res += 1

代码如下
class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] sumArr = new int[nums.length + 1];
        sumArr[0] = 0;
        //prefix sum array
        for(int i = 0; i < nums.length; i++){
            sumArr[i + 1] = sumArr[i] + nums[i];
        }
        int count = 0;
        for(int i = 0; i < sumArr.length; i++){
            for(int j = 0; j < i; j++){
                if(sumArr[i] - sumArr[j] == k) count += 1;
            }
        }
        return count;
    }
}

我们发现这个算法，其实还是暴力解法，只不过是采用了prefix sum的思想。 而且还使用了额外的空间复杂度
time o(n^2)  1200ms 左右
space o(n)

那么怎么优化那？

我突然想起来，刚才看到的最优解，HASHMAP! 茅塞顿开的感觉，真滴是爽！
思路
1. 设置hashMap key是prefix sum  value 是使用过多少次 （每使用一次，说明就有一次结果）
2. 从头跑到尾
    a. curSum += nums[i]
    b. 如果map中存在key 是  curSum - k  那么说明就有结果
    下面这一步 在 java中用一行就能解释 文字需要两个logic
          1.  如果不存在，就放入curSum 至 map中 并把value 设置为1
          2.  如果已经存在， 那么就把value + 1 （负数的情况 所以curSum 会出现重复）

Time O(N)
Space O(n)

个人建议 面试遇到 从第二个 演到 第三个 时间掐住 半小时比较好。不然 从第一种直接暴力解 到第三种hashmap 优化 时间上我们演不了怎么快
只要能把后面两个演好， 绝对是个Hire
刷过题的面试官会心一笑，小伙子挺会演。为你拍灯
傻白甜面试官会心一笑，大腿大腿抱定了，为你拍灯

如果刷过题，我一般都是冲着最优解去的，面试官出的高频题，像狗家很多followup，演半小时直接followup都做不完。脸家45分钟两道题，就期望你一上来就最优解，否则45分钟两道题做不完。

我竟然看不懂

你leetcode第一题two sum是怎么解的

现在还有没刷过题的面试官呢？