C++에서 최대 크기 부분배열 합은 k와 같음

<시간/>

nums라는 배열과 대상 값 k가 있다고 가정하고 k가 되는 하위 배열의 최대 길이를 찾아야 합니다. 존재하지 않으면 대신 0을 반환합니다.

따라서 입력이 nums =[1, -1, 5, -2, 3], k =3과 같으면 하위 배열 [1, - 1, 5, -2]의 합이 다음과 같이 출력은 4가 됩니다. 3이고 가장 깁니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ret :=0
하나의 맵 정의
n :=숫자 크기
온도 :=0, m[0] :=-1
initialize i :=0의 경우, i
- 임시 :=임시 + 숫자[i]
- (temp - k)가 m인 경우 -
  - ret :=ret 및 i의 최대값 - m[temp - k]
- temp가 m이 아닌 경우 -
  - m[temp] :=i
리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxSubArrayLen(vector<int<& nums, int k) {
      int ret = 0;
      unordered_map <int, int> m;
      int n = nums.size();
      int temp = 0;
      m[0] = -1;
      for(int i = 0; i < n; i++){
         temp += nums[i];
         if(m.count(temp - k)){
            ret = max(ret, i - m[temp - k]);
         }
         if(!m.count(temp)){
            m[temp] = i;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int< v = {1,-1,5,-2,3};
   cout << (ob.maxSubArrayLen(v, 3));
}

입력

[1,-1,5,-2,3], 3