一道决定面试成败的算法题

太过爱你忘了你带给我的痛 2023-05-30 08:44 111阅读 0赞

### 文章目录 ###

*   *   *   *  理解题意
             *  思考过程
             *  求数组中和等于给定值的最长子数组
             *  代码实现
             *  总结

前几天公司社招面了几个同学，和其它面试官交流后听到了其中一个同事常用的一个算法题，这道算法题几乎决定了能否通过该面试官，题目比较有意思，是这样的，给定一个数组，求出奇数和偶数个数相同的最长连续子数组，有的同学可能听过这个题目，没有听过的同学可以先自己想想该怎么解决这个问题。

#### 理解题意 ####

这是什么意思呢，假设给定数组\[2,2,2,3,4,5,6,7,7,7\]，那么奇数和偶数个数相同的最长连续子数组是\[2,2,3,4,5,6,7,7\]，这个数组中奇数和个数和偶数的个数相等都是4个。再假设给定数组\[1,2,3,4,5,6\]，那么奇数和偶数个数相同的最长连续子数组是其本身，整个数组奇数和偶数的个数相等是3个，现在你应该明白题目的意思了吧。

#### 思考过程 ####

这个题目我还是第一次听到，因此开始想如果我在面试时遇到这个题目该如何求解呢？我的第一反应是记录奇数和偶数个数是比较繁琐的过程，**能不能把问题转化一下呢**？

反正是计算奇数或者偶数的个数，那么干脆就先对数组处理一下，把奇数修改为1，把偶数修改为0，那么对于数组\[2,2,2,3,4,5,6,7,7,7\]经过上述转换后就变为了\[0,0,0,1,0,1,0,1,0,1,1,1\]，然后我们来看看问题是不是变的简单了一些。

实际上有的同学可能已经看出来了，把奇数修改为1，把偶数修改为0并没有简化问题，我们依然需要计算1的个数和0的个数，这样的转换没有达到简化问题的目的。

还有没有更好的转换方法吗，奇数的个数和偶数的个数相同可以等价转换为什么呢？大家可以先自己想一想这个问题。

也许有的同学已经想出来了，上述过程中既然把奇数修改为了1，那么我们可以把偶数修改为-1，这样奇数的个数和偶数的个数相同就等价转换为了这个子数组的和为0，这样的转换极大的简化了问题的求解过程。

因此我们可以看到**问题等价转换**的思维方式在求解算法这类问题时是非常有用的。

现在我们知道了这个问题可以转换为求“和为0的最长连续子数组”，在这里需要意识到和为0是一个非常具体的问题，**有时候求解这类具体的问题可能没有求解通用的问题**来的简单，那么什么是通用的问题呢？也就是说我们不去求解“和为0的最长连续子数组”，而是试图求解“和为给定值的最长连续子数组”。

#### 求数组中和等于给定值的最长子数组 ####

现在我们已经将最初的求奇数和偶数个数相同的最长连续子数组转换为了求和等于给定值的最长子数组，那么这个新的问题该如何解决呢？

我们首先来想最简单的解法，只要找出所有的子数组，然后计算出每个子数组的和并判断是否等于给定值，如果等于给定值并且其长度大于之前的记录那么更新记录，这种解法非常简单，但是时间复杂度也很高，为O(n^3)，有没有更好的解决吗？答案是肯定的。

实际上对于最后求解的子数组**必然是以某个元素为结尾的**，因此对于数组中的每个元素我们去计算以该元素为结尾的子数组是否其和等于给定值，这句话非常重要，是解决问题的关键所在。比如对于数组：

\[1,2,3,4,5,6,7\]

我们依次去计算以1为结尾的子数组其和是否等于给定值，以2为结尾的子数组其和是否等于给定值，以3为结尾的子数组其和是否等于给定值。。如果有那么记录下该数组的长度并与之前的记录相比较。

那么这里的问题是，我们怎么能知道以比如6为结尾的子数组其和是否等于给定值呢？

让我们来仔细的看一下这个问题，对于数组\[1,2,3,4,5,6,7\]，以6为结尾的子数组有多少可能性？

\[1,2,3,4,5,6\] \[2,3,4,5,6\] \[3,4,5,6\] \[4,5,6\] \[5,6\] \[6\]

可以看到有这么多子数组，我们要一个一个的去计算每个子数组的和吗，这不又退回之前的解法了吗？别着急，你马上就会明白的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zNzM4MjMxOQ_size_16_color_FFFFFF_t_70_pic_center]  
如图所示，我们需要求解的是B，但是实际上B = C - A，**因此我们又一次对问题进行了转化**，B不是很容易就能求解出来，但是对于C和A的求解就非常简单了。

现在你应该明白了吧，对于以比如6为结尾的子数组，我们该如何计算呢？

sum(1,2,3,4,5,6) sum(1,2,3,4,5,6) - sum(1) sum(1,2,3,4,5,6) - sum(1,2) sum(1,2,3,4,5,6) - sum(1,2,3) sum(1,2,3,4,5,6) - sum(1,2,3,4) sum(1,2,3,4,5,6) - sum(1,2,3,4,5)

sum(1,2,3,4,5,6)是一个确定的值，这个非常简单，而对于sum(1)，sum(1,2)，sum(1,2,3)，sum(1,2,3,4)，sum(1,2,3,4,5)来说我们真的有必要一个一个的去减一下吗？当然是没有必要的，我们可以把这些值放到一个map中，然后用sum(1,2,3,4,5,6)减去给定的值t，然后用这个值去map中查一下，如果有就说明存在这样的一个子数组。

接下来对于sum(1)，sum(1,2)，sum(1,2,3)，sum(1,2,3,4)，sum(1,2,3,4,5)的计算也非常简单，原因就在于对于sum(1,2,3,4,5,6)来说，sum(1,2,3,4,5,6) = sum(1,2,3,4,5) + 6，因此我们只需要遍历一边就能计算出所有的值，这就是**累加和**的概念，利用的就是前一个数组的和，本质上这也是动态规划思想的重要特征之一，即，充分利用上一步的计算结果。

这种方法的时间复杂度为O(n)，相比最开始的O(n^3)有了很大的提高，有了这些分析就可以写代码了。

#### 代码实现 ####

int get_length(vector<int>& arr, int target) {
        if (arr.size() == 0)
            return 0;
        map<int,bool>m_exist;
        map<int,int> m_pos;
        int r = 0;
        int sum = 0;
        m_exist[0] = true; // 在数组的开头放入假想的数字0
        m_pos[0] = -1;
    
        for (int i=0;i<arr.size();i++) {
            sum += arr[i];
            if (!m_exist[sum]) {
                m_exist[sum] = true;
                m_pos[sum] = i;
            }
            if (m_exist[sum - target]) 
                r = max(r, i - m_pos[sum - target]);
        }
        return r;
    }

代码相对简单，使用两个map，一个map用来记录从0开始的所有子数组的和，另一个map用来记录对应的子数组结尾位置。注意到有这样两行代码：

m_exist[0] = true;
     m_pos[0] = -1;

其意图是在数组中放入假想的0，为的就是处理这样的一种特殊情况：假设给定数组\[1,2,3\]，求和为6的最长子数组，特殊之处在于该子数组的起始位置是0。

剩下的就很简单了，仅仅就是上述分析的代码实现，不再赘述。

问题还没有解决完，最开始的问题是求解出奇数和偶数个数相同的最长连续子数组，有了get\_length这个函数剩下的就很简单了：

int solution(vector<int>& arr) {
        if (arr.size()==0)
            return 0;
        for(int i=0;i<arr.size();i++){
            if (arr[i] % 2 == 0)
                arr[i] = 1;
            else
                arr[i] = -1;
        }
    
        return get_length(arr, 0);
    }

将数组中偶数转为-1，偶数转为1，然后调用get\_length函数即可。

注意，该算法的时间复杂度为O(n)，如果我们认为map的查找效率为O(1)的话。这个时间复杂度通过面试肯定是没有问题的。

#### 总结 ####

对于算法问题，不要试图“记住”问题的答案，题目千变万化，试图"记住"每一个算法题答案是不现实的，但是这些算法题目背后的解题思想就那么多，你需要掌握的是**解决算法问题的思维模式**而不是仅仅背过几个答案，在这个算法题目中实际上我们已经看到了这其中的一种思维模式，那就是问题的**等价转换**，实际上这也是上学读书时常用到的解题方法，对此我们都曾经烂熟于心的，这些才是值得掌握的东西而不是几个算法题的解法，希望这个题目能给你一些启发。

不要去“背”算法题，要有自己的方法论

更多计算机内功文章，欢迎关注微信公共账号：**码农的荒岛求生**。

![在这里插入图片描述][I0JBQkFCMA_pic_center]  
***彻底理解操作系统系列文章***  
1，[什么程序？][Link 1]  
2，[进程？程序？傻傻分不清][Link 2]  
3，[程序员应如何理解内存：上篇][Link 3]  
4，[程序员应如何理解内存：下篇][Link 4]

> ***计算机内功决定程序员职业生涯高度***

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zNzM4MjMxOQ_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20191108130643244.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zNzM4MjMxOQ==,size_16,color_FFFFFF,t_70#pic_center
[I0JBQkFCMA_pic_center]: https://img-blog.csdn.net/20181010212835250?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zNzM4MjMxOQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==#pic_center
[Link 1]: https://blog.csdn.net/github_37382319/article/details/94867431
[Link 2]: https://blog.csdn.net/github_37382319/article/details/99656274
[Link 3]: https://blog.csdn.net/github_37382319/article/details/99688951
[Link 4]: https://blog.csdn.net/github_37382319/article/details/99688821