建设工程网站新专家入库,wordpress数据库清理sql,建设网站iss,如何做网站页面赚钱前缀和
前缀和指数组的前 N项之和#xff0c;是个比较基础的算法
例题
面试题 17.05. 字母与数字
给定一个放有字母和数字的数组#xff0c;找到最长的子数组#xff0c;且包含的字母和数字的个数相同。 返回该子数组#xff0c;若存在多个最长子数组#xff0c;返回左…前缀和
前缀和指数组的前 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[startmaxlen]的部分。
代码
class Solution {
public:vectorstring findLongestSubarray(vectorstring array) {int narray.size();int sum0;int maxlen0;int start-1;unordered_mapint,int indices;indices[0]-1;for(int i0;in;i){if(isalpha(array[i][0])){sum;}else{sum--;}if(indices.find(sum)indices.end()){indices[sum]i;}else{if(i-indices[sum]maxlen){maxleni-indices[sum];startindices[sum]1;}}}if(maxlen0) return {};return vectorstring(array.begin()start,array.begin()startmaxlen);}
};209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, …, 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, vectorint nums) {int nnums.size();int minlenn1;vectorint presum(n1,0);//presum[i]是从0加到i-1for(int i0;in;i){presum[i1]presum[i]nums[i];}for(int i0;in;i){int li1,rn;while(lr){int m(lr)/2;if(presum[m]-targetpresum[i]){lm1;}else{rm;}}if(presum[l]-targetpresum[i]){minlenmin(l-i,minlen);}}if(minlenn) return 0;else return minlen;}
};class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int nnums.size();int l0,r0;int sumnums[0],minlenn1;while(rn){while(sumtargetrn){if(rn) sumnums[r];}if(sumtarget){minlenmin(minlen,r-l1);sum-nums[l];l;}else break;}return minlenn?minlen:0;}
};
