Kích thước tối đa của mảng con Tổng bằng k trong C ++

Giả sử chúng ta có một mảng gọi là nums và một giá trị đích k, chúng ta phải tìm độ dài tối đa của một mảng con có tổng bằng k. Nếu không có bất kỳ, hãy trả về 0 để thay thế.

Vì vậy, nếu đầu vào giống như nums =[1, -1, 5, -2, 3], k =3, thì đầu ra sẽ là 4, vì mảng con [1, - 1, 5, -2] tính bằng 3 và là dài nhất.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0

• Xác định một bản đồ m

• n:=kích thước của nums

• tạm thời:=0, m [0]:=-1

• để khởi tạo i:=0, khi i

  • temp:=temp + nums [i]

  • nếu (temp - k) tính bằng m, thì -

    • ret:=tối đa ret và i - m [temp - k]

  • nếu nhiệt độ không tính bằng m, thì -

    • m [temp]:=i

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

4