这两周LeetCode的周周赛都有一道解法类似的题目： 525. Contiguous Array 这道题是有一个数组全是0,1两种数字，然后找出其中最长的一段子数组，子数组中0和1的数量相等。 523. Continuous Subarray Sum因为还是比赛题，所以正式版链接还没出来，等出来了再补上 这道题是判断一个数组，其是否存在一个子数组和，子数组和为选定值k的倍数
其实子数组和的问题，知道标准解法之后，还是挺简单的，只不过不知道的话，可能不太知道这里的trick，特此记录一下。
关于子数组和的问题【这里的子数组指的是连续的一段子数组】，一个最基础的问题是：给一个数组，然后判断其中的子数组和是否为某一个特定的值k。 这道题的解法是：一次记录出
所以对于525题，这道题本质上可以看成，把所有的0看成-1，所有1看成1，然后找其中最长的子数组和为0的长度。 所以程序如下：
int findMaxLength(vector<int>& nums) { int sum = 0; map<int,vector<int> > res; res[0].push_back(-1); int max_num = 0; for(int i=0;i<nums.size();i++){ if(nums[i] == 1) sum++; else sum--; res[sum].push_back(i); } for(auto x:res){ max_num = max(x.second.back()-x.second.front(),max_num); } return max_num;}而523题则是因为k的倍数也可以，所以，就求和的时候再模一下k，所以归在同一个vector里的数，其相减就满足k的正整数倍。代码如下：
bool checkSubarraySum(vector<int>& nums, int k) { //k = 0因为0不能做余数和除数，所以需要单独判断 if(k == 0){ for(int i=1;i<nums.size();i++){ if(nums[i-1] == 0&&nums[i] == 0) return true; } return false; } map<int,vector<int>> res; int sum = 0; res[0].push_back(-1); for(int i=0;i<nums.size();i++){ sum = (sum+nums[i])%k; res[sum].push_back(i); } for(auto x:res){ if(x.second.size()>1&&x.second.back()-x.second.front()>1) return true; } return false;}新闻热点
疑难解答
