ขนาดสูงสุดของ Subarray Sum เท่ากับ k ใน C++

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และค่าเป้าหมาย k เราต้องหาความยาวสูงสุดของอาร์เรย์ย่อยที่รวมเป็น k หากไม่มีอยู่ ให้คืนค่า 0 แทน

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[1, -1, 5, -2, 3], k =3 ผลลัพธ์จะเป็น 4 เช่นเดียวกับ subarray [1, - 1, 5, -2] รวมเป็น 3 และยาวที่สุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ยกเลิก :=0

• กำหนดหนึ่งแผนที่ m

• n :=ขนาดของ nums

• อุณหภูมิ :=0, m[0] :=-1

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • temp :=temp + nums[i]

  • ถ้า (temp - k) อยู่ในหน่วย m แล้ว −

    • ret :=สูงสุดของ ret และ i - m[temp - k]

  • ถ้าอุณหภูมิไม่เป็น 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

ผลลัพธ์

4