【題解】LeetCode 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

【題目敘述】https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/

class Solution {
public:
    int minSumOfLengths(vector<int>& a, int tar) {
        unordered_map <int, int> mp;
        int mn[100005], pre = 0, ans = 200005;
        mn[0] = 200005;
        mp[0] = 0;
        for (int i = 1; i <= a.size(); i++){
            pre += a[i-1];
            if (mp.count(pre-tar)){
                mn[i] = i-mp[pre-tar];
                ans = min(ans, mn[i]+mn[mp[pre-tar]]);
                mn[i] = min(mn[i-1], i-mp[pre-tar]);
            }
            else mn[i] = mn[i-1];
            mp[pre] = i;
        }
        if (ans == 200005) return -1;
        else return ans;
    }
};
分享本文 Share with friends