威海高區(qū)有沒有建設(shè)局的網(wǎng)站uc搜索引擎入口
前綴和
前綴和指數(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;}
};