给定一个数组和一个正整数N,求一个和小于N的最长连续子数组头条算法题相关代码//请把代码文本粘贴到下方(请勿用图片代替代码)大神!!!思路,代码,注释
2 回答
千万里不及你
TA贡献1784条经验 获得超9个赞
可以用动态规划的思想去看,设S(i)为以第i个元素结尾的和小于N的最长连续数组设len(i)为S(i)的长度设sum(i)为S(i)的和边界:len(0)=arr[0]sum(0)=arr[0](对于不可取的数(比N大)我们也把和记上) 当计算S(i)时,如果arr[i]>=N,那么舍弃否则将arr[i]加入S(i)中(目前len(i)为1,sum(i)为arr[i])不停归并S(i)左边相邻的S(i-len(i)),直到sum(i)不再小于N这里需要注意对于一些比N大的项原来不可取,现在也有可能取到最后从S(i)最左的元素往右筛除,缩小数组直到总和小于N最后根据最长的len返回数组即可functionlsa(arr,n){if(arr.length<=0){return[]}//1constlen=[arr[0]constsum=[arr[0]] for(leti=1;iif(arr[i]>=n){//2 len[i]=0sum[i]=arr[i]}else{//3//3.1len[i]=1sum[i]=arr[i]//3.2for(letj=i-len[i];j>=0&&sum[i]sum[i]+=sum[j] len[i]+=len[j]||1//3.2.1}//3.3for(letj=i+1-len[i];j=n;j++){len[i]-=1sum[i]-=arr[j]}}}constmax=len.reduce((max,l,i)=>l>len[max]?i:max,0)returnarr.slice(max+1-len[max],max+1)}
添加回答
举报
0/150
提交
取消