前缀和部分题目

前缀和

前缀和指数组的前 N项之和，是个比较基础的算法

例题

面试题 17.05. 字母与数字

给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

示例 1:
输入: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”,“H”,“I”,“J”,“K”,“L”,“M”]
输出: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”]

示例 2:
输入: [“A”,“A”]
输出: []

提示：
array.length <= 100000

思路

使用前缀和+哈希
为字母则取1，数字为-1，即要求和为0的最大子数组。
前缀和表示第i个数及之前的所有数的和。哈希存储前缀和c第一次出现的位置i，循环时维护一个maxlen表示最大的子数组长度，start表示最长子数组起始下标。
初始化时，前缀和为0，下标为-1。遍历到i时，前缀和为sum，如果此时哈希表中没有关于前缀和为sum的记录，则更新indices[sum]=i。如果已有，则对比maxlen和i-indices[sum]，如果i-indices[sum]较大，则maxlen更新为i-indices[sum]，start更新为indices[sum]+1。
如果maxlen不为0，返回array中array[start]到array[start+maxlen]的部分。

代码

class Solution {
public:vector<string> findLongestSubarray(vector<string>& array) {int n=array.size();int sum=0;int maxlen=0;int start=-1;unordered_map<int,int> indices;indices[0]=-1;for(int i=0;i<n;i++){if(isalpha(array[i][0])){sum++;}else{sum--;}if(indices.find(sum)==indices.end()){indices[sum]=i;}else{if(i-indices[sum]>maxlen){maxlen=i-indices[sum];start=indices[sum]+1;}}}if(maxlen==0) return {};return vector<string>(array.begin()+start,array.begin()+start+maxlen);}
};

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

思路

首先计算前缀和，presum[i]表示从0加到i-1的和，
对于遍历每个子数组的起始点nums[i]，用二分搜索找到presum[j]-presum[i]大于或等于target的第一个下标j，遍历过程中维护最短子数组的长度minlen。

或者用滑动窗口做

代码

//前缀和+二分搜索
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int minlen=n+1;vector<int> presum(n+1,0);//presum[i]是从0加到i-1for(int i=0;i<n;i++){presum[i+1]=presum[i]+nums[i];}for(int i=0;i<n;i++){int l=i+1,r=n;while(l<r){int m=(l+r)/2;if(presum[m]-target<presum[i]){l=m+1;}else{r=m;}}if(presum[l]-target>=presum[i]){minlen=min(l-i,minlen);}}if(minlen>n) return 0;else return minlen;}
};

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int l=0,r=0;int sum=nums[0],minlen=n+1;while(r<n){while(sum<target&&r<n){if(++r<n) sum+=nums[r];}if(sum>=target){minlen=min(minlen,r-l+1);sum-=nums[l];l++;}else break;}return minlen<=n?minlen:0;}
};