剑指Offer（数据结构与算法面试题精讲）C++版——day4

题目一：和为k的子数组

    结合前面着重阐述的双指针法这一经典的算法技巧，我们在面对当前的问题时，很自然且清晰地能够联想到运用双指针来进行处理。于是，我们设置了左指针 p 和右指针 q ，让它们从数组的最左端开始，逐步向右进行遍历操作。在这个过程中，由指针 p 和指针 q 之间所涵盖的数组元素共同构成了一个子数组。算法的核心逻辑在于对这个子数组的和进行判断与处理。当子数组的和小于给定的数值 k 时，为了使子数组的和能够更接近或达到 k ，我们选择将指针 q 朝着右方移动，从而纳入更多的数组元素，期望增加子数组的和；而当子数组的和大于 k 时，为了减小子数组的和，我们会将指针 p 向右移动，剔除部分数组元素。然而，这种看似简洁高效的方法却存在着一个不容忽视的局限性。该方法仅仅适用于数组元素均为正整数的情况。因为如果数组中存在非正整数，当执行向右移动指针的操作时，很可能会出现子数组的和变得更小的情况，这样一来，原本通过移动指针来增加子数组和值的目的就无法达成了，也就导致这种方法在处理包含非正整数的数组时失去了有效性。
    因此，需要考虑使用其他方法，如果是直接使用蛮力法，那么需要借助于数组下标，差分出O(n^2)种左右不同边界，对于每一个子数组，为了计算和，还需要O(n)时间，因此蛮力法的时间复杂度为O(n^3)，还是比较高的。分析发现，可以借助于数列和的特点来优化时间复杂度，也是一种空间换时间的方法，记Si表示数组从下标0-i之间的所有元素的和，那么在定界之后，比如说子数组的左右边界对应在数组中的下标为i和j，那么这段子数组的和值即为Sj-Si。这样得到的时间复杂度为O(n^2)，最终得到的代码如下：

# include <iostream>
# include <algorithm>
using namespace std;
int findChildArrCount(int arr[],int len,int k) {int count=0,sum=0;int arrSum[len]= {0};for(int i=0; i<len; ++i) {sum+=arr[i];arrSum[i]=sum;}for(int i=0; i<len; ++i) {for(int j=i; j<len; ++j) {if((i==0&&arrSum[j]==k)||((arrSum[j]-arrSum[i-1])==k)) {count++;}}}return count;
}
int main() {int arr[]= {1,1,1};int len=sizeof(arr)/sizeof(arr[0]);int k=2;cout<<"这样的数组个数为："<<findChildArrCount(arr,len,k);return 0;
}

题目二：0和1个数相同的子数组

    我们能够从前面题目一中关于子数列的和的相关内容获取灵感，从而想到一个简洁而有效的思路。就像之前处理问题那样，我们还是聚焦于计算数组中特定元素的和，这里着重考虑的是与统计偶数个数相关的和值计算。具体来说，我们设定
Si为数组从起始下标 0 到下标 i 这一区间内所有元素的总和，通过这种方式来构建一个便于后续分析的和值序列。
    当我们对数组进行定界操作时，会确定子数组的左右边界，不妨设子数组的左边界在数组中的下标为 i ，右边界下标为 j 。基于前面定义的 Si​，我们可以清晰地得出，这个子数组的和值能够通过 Sj​−Si 计算出来。
    接下来，我们需要对数组进行第二次遍历。在这次遍历过程中，我们会仔细检查定界指针 i 和 j 之间的子数组的元素和情况。这里存在两个关键的判断条件，缺一不可。一方面，定界指针 i 和 j 之间的子数组元素和必须恰好等于 (j−i+1)/2 ，这是由于我们要寻找的子数组中 0 和 1 的数量相等，所以其元素和必然是子数组长度的一半。另一方面，该子数组的长度必须是偶数，因为只有长度为偶数的情况下，才有可能实现 0 和 1 的个数相等这一目标。只有当这两个条件同时满足时，才能判定这样的子数组符合我们预先设定的要求。
    这种解决问题的方法在时间和空间复杂度上都具有明显的优势，其开销相对较小。从具体的操作流程来看，仅仅需要对数组进行两次遍历即可。第一次遍历主要是对数组元素进行求和统计，为后续的判断提供必要的数据支撑；第二次遍历则是在第一次遍历所得和值的基础上，逐一检查每个子数组的和是否恰好等于数组长度的一半，以此来筛选出符合条件的子数组。基于以上完整的思路，我们最终能够编写出相应的代码。

# include <iostream>
# include <algorithm>
using namespace std;
int findMaxLength(int arr[],int len) {int sum=0,maxLen=0;bool condition1,condition2;int arrSum[len]= {0};for(int i=0; i<len; ++i) {sum+=arr[i];arrSum[i]=sum;}for(int i=0; i<len; ++i) {for(int j=i; j<len; ++j) {condition1=(j-i+1)%2==0;//子数组的个数为偶数condition2=(i==0&&arrSum[j]==j/2)||(arrSum[j]-arrSum[i-1]==(j-i+1)/2);//满足和为个数的一半 if(condition1&&condition2&&(j-i+1)>maxLen) {//满足上述2个条件且超过当前最大子数组长度 maxLen=j-i+1;}}}return maxLen;
}
int main() {int arr[]= {0,1,0,1};int len=sizeof(arr)/sizeof(arr[0]);cout<<"这样的数组最大长度为："<<findMaxLength(arr,len);return 0;
}

题目三：左右两边子数组的和相等

    结合前面两道题我们会发现，这种方法还特别好用，利用空间换时间。我们可以立即想到一个思路，第一次遍历数组，统计Si，那么对于给定的一个枢轴元素取为arr[k]，我们只需要比较S(k-1)-S(i-1) 和S(len-1)-S(k)是否相等即可。
    这样需要消耗O(n)的空间复杂度，分析发现，其实我们只需要去统计整个数组的和（记为sum），以及前Si，那么后半段的和可以利用sum-arr[k]-S(k-1)拿到，这样空间复杂度就优化成了O(1)了。最终得到的代码如下：

# include <iostream>
# include <algorithm>
using namespace std;
int findPivotIndex(int arr[],int len) {int sum=0,tmpSum=0;for(int i=0; i<len; ++i) {//统一次总和sum+=arr[i];}for(int i=0; i<len-1; ++i) {tmpSum+=arr[i];//枢轴左半边的和if(i==0||i==len-1)continue;//排除枢轴在边界的情况if(tmpSum==sum-arr[i+1]) {return i;}}return -1;
}
int main() {int arr[]= {1,7,3,6,2,9};int len=sizeof(arr)/sizeof(arr[0]);cout<<"枢轴元素的下标为："<<findPivotIndex(arr,len);return 0;
}

    这里补充两点说明：
（1）题目三中对于子数组，可能有些OJ平台会考虑到空数组的情况，需要根据实际判题结果来调整，这里是以子数组不能为空来编写的；
（2）需要注意一点，对于数组取和，最好使用long long来存储，可能有些测试数据的和值超过了INT的最大范围。
    我是【Jerry说前后端】，本系列精心挑选的算法题目全部基于经典的《剑指 Offer（数据结构与算法面试题精讲）》。在如今竞争激烈的技术求职环境下，算法能力已成为前端开发岗位笔试考核的关键要点。通过深入钻研这一系列算法题，大家能够系统地积累算法知识和解题经验。每一道题目的分析与解答过程，都像是一把钥匙，为大家打开一扇通往高效编程思维的大门，帮助大家逐步提升自己在数据结构运用、算法设计与优化等方面的能力。
    无论是即将踏入职场的应届毕业生，还是想要进一步提升自己技术水平的在职开发者，掌握扎实的算法知识都是提升竞争力的有力武器。希望大家能跟随我的步伐，在这个系列中不断学习、不断进步，为即将到来的前端笔试做好充分准备，顺利拿下心仪的工作机会！快来订阅吧，让我们一起开启这段算法学习之旅！