前綴和

前綴和指數(shù)組的前 N項(xiàng)之和，是個(gè)比較基礎(chǔ)的算法

例題

面試題 17.05. 字母與數(shù)字

給定一個(gè)放有字母和數(shù)字的數(shù)組，找到最長的子數(shù)組，且包含的字母和數(shù)字的個(gè)數(shù)相同。
返回該子數(shù)組，若存在多個(gè)最長子數(shù)組，返回左端點(diǎn)下標(biāo)值最小的子數(shù)組。若不存在這樣的數(shù)組，返回一個(gè)空數(shù)組。

示例 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，數(shù)字為-1，即要求和為0的最大子數(shù)組。
前綴和表示第i個(gè)數(shù)及之前的所有數(shù)的和。哈希存儲前綴和c第一次出現(xiàn)的位置i，循環(huán)時(shí)維護(hù)一個(gè)maxlen表示最大的子數(shù)組長度，start表示最長子數(shù)組起始下標(biāo)。
初始化時(shí)，前綴和為0，下標(biāo)為-1。遍歷到i時(shí)，前綴和為sum，如果此時(shí)哈希表中沒有關(guān)于前綴和為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. 長度最小的子數(shù)組

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。
找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0 。

示例 1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。

示例 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

進(jìn)階：
如果你已經(jīng)實(shí)現(xiàn) O(n) 時(shí)間復(fù)雜度的解法, 請嘗試設(shè)計(jì)一個(gè) O(n log(n)) 時(shí)間復(fù)雜度的解法。

思路

首先計(jì)算前綴和，presum[i]表示從0加到i-1的和，
對于遍歷每個(gè)子數(shù)組的起始點(diǎn)nums[i]，用二分搜索找到presum[j]-presum[i]大于或等于target的第一個(gè)下標(biāo)j，遍歷過程中維護(hù)最短子數(shù)組的長度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;}
};