Maximum Size Subarray Sum Equals K - Đoạn con dài nhất tổng bằng K

Cho mảng nums và giá trị k. Tìm độ dài lớn nhất của đoạn con liên tiếp có tổng bằng k. Không có thì trả 0.

Ví dụ: nums = [1,-1,5,-2,3], k=3 → 4 (đoạn [1,-1,5,-2]).

Giải thuật (Prefix Sum + Hash Map)

Lưu prefixSum -> index sớm nhất. Với tổng tiền tố sum tại chỉ số i, nếu sum - k đã có trong map, đoạn từ map[sum-k]+1 đến i có tổng k. Cập nhật độ dài lớn nhất.

Cài đặt C++

#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 sum = 0;
        m[0] = -1;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            if (m.count(sum - k))
                ret = max(ret, i - m[sum - k]);
            if (!m.count(sum))
                m[sum] = i;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,-1,5,-2,3};
    cout << ob.maxSubArrayLen(v, 3);
    return 0;
}

Đầu vào

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

Đầu ra

4