home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Maximum Size Subarray Sum Equals k ใน C++

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

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

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

  • ret := 0

  • กำหนดแมป m

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

  • temp := 0, m[0] := -1

  • ลูป i := 0 ถึง n-1 ทำ −

    • temp := temp + nums[i]

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

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

    • ถ้า temp ไม่อยู่ใน m แล้ว −

      • m[temp] := i

  • คืนค่า ret

ตัวอย่าง

ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −

#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