力扣1124. 表现良好的最长时间段

这一题我看到数据范围是10^4，暗自窃喜能用双重循环，看题目是典型的前缀和+哈希。不过需要一个转换将大于8小时的转化为1，其他都为-1，方便计算，之前的题目中也有这种方法。
那这样就简单了

class Solution {
public:int sum[100005];
unordered_map<int,int> mp;int longestWPI(vector<int>& hours) {for(int i=0;i<hours.size();i++){if(hours[i]>8)sum[i+1]=sum[i]+1;elsesum[i+1]=sum[i]-1;}int ans=0;mp[0]=0;for(int j=1;j<=hours.size();j++){for(auto it=mp.begin();it!=mp.end();it++){if(sum[j]-(it->first)>0){ans=max(ans,j-it->second);}}mp[sum[j]]=j;}return ans;}
};

这样是正常的前缀和+哈希，会出现错误
因为我们在枚举的过程中遇到一个前缀和就更新哈希表，这会导致相同的前缀和值它的索引往后放，也就会导致在计算子数组的长度时会变小，因此我们需要做的就是在遇到相同的值的时候不要更新哈希表即可。
正确代码如下：

class Solution {
public:int sum[100005];
unordered_map<int,int> mp;int longestWPI(vector<int>& hours) {for(int i=0;i<hours.size();i++){if(hours[i]>8)sum[i+1]=sum[i]+1;elsesum[i+1]=sum[i]-1;}int ans=0;mp[0]=0;for(int j=1;j<=hours.size();j++){for(auto it=mp.begin();it!=mp.end();it++){if(sum[j]-(it->first)>0){ans=max(ans,j-it->second);}}if(!mp.count(sum[j]))mp[sum[j]]=j;}return ans;}
};

时间复杂度为O（n^2）虽然轻松通过，但不是最优解
最优解需要我们领会sum取1和0的时候不用再像其他情况一样，算子数组
而是只要sum>0，那么子数组的长度最长就是j 因为存在sum[0]=0
所以我们可以分情况讨论
当sum>0的时候，可以直接更新ans
当sum<=0的时候，我们需要从哈希表中取出 sum-1的值
为啥非要取sum-1，因为sum【j】-sum【i】=子数组，所以必须sum【i】 必须比sum[j]要小.
那为啥不取其他比sum【j】的值呢，因为该前缀和在求的过程中是一步一步变小或者变大的，比如如果sum[j]=-2,那么sum=-1的索引一定在它左边，也就是说更小的前缀和在右边，而sum-1在构成子数组和为》0的所有情况中，构成的子数组的长度最大，因为它在最左边。
所以我们就可以写代码了，还要注意遇到相同的值的时候不要更新哈希表。

class Solution {
public:int sum[100005];
unordered_map<int,int> mp;int longestWPI(vector<int>& hours) {for(int i=0;i<hours.size();i++){if(hours[i]>8)sum[i+1]=sum[i]+1;elsesum[i+1]=sum[i]-1;}int ans=0;mp[0]=0;for(int j=1;j<=hours.size();j++){if(sum[j]>0){ans=max(ans,j);}else{if(mp.count(sum[j]-1)){ans=max(ans,j-mp[sum[j]-1]);}}if(!mp.count(sum[j])){mp[sum[j]]=j;}}return ans;}
};

时间复杂度为O(n)为最优解。