?？皖}霸 [ 未排序數組中累加和為給定值的最長子數組長度] C++題解/答案

題目描述

給定一個無序數組arr, 其中元素可正、可負、可0。給定一個整數k，求arr所有子數組中累加和為k的最長子數組長度

題解：

先求出前綴和
然后用map來記錄第i位的前綴和
要找和為k的子數組
我們直接看(第i位前綴和+k)是否存在，如果存在map的值指向的第j位，那長度就是j-i+1
取最大值
當然還有可能前綴和本身就是k，記得不要忘了這種情況

代碼：

#include<unordered_map> class Solution { public:/*** max length of the subarray sum = k* @param arr int整型vector the array* @param k int整型 target* @return int整型*/int maxlenEqualK(vector<int>& arr, int k) {// write code hereif(arr.size()==0)return 0;vector<int>w(arr.size(),0);w[0]=arr[0];for(int i=1;i<arr.size();i++){w[i]=w[i-1]+arr[i];}int maxx=0;unordered_map<int,int> ump;for(int i=0;i<arr.size();i++){ump[w[i]]=i;}int ans=0;for(int i=0;i<arr.size();i++){if(ump.count(w[i]+k)){ans =max(ans, ump[w[i]+k]-i);}}if(ump.count(k)) ans = max(ans, ump[k]+1);return ans;} };

總結

以上是生活随笔為你收集整理的牛客题霸 [ 未排序数组中累加和为给定值的最长子数组长度] C++题解/答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。