1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

class Solution {
    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        int[] best = new int[n];
        Arrays.fill(best, Integer.MAX_VALUE);
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0, ans = Integer.MAX_VALUE, curBest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (map.containsKey(sum - target)) {
                int j = map.get(sum - target);
                int len = i - j;
                if (j >= 0 && best[j] != Integer.MAX_VALUE) {
                    ans = Math.min(ans, len + best[j]);
                }
                curBest = Math.min(curBest, len);
            }
            best[i] = curBest;
            map.put(sum, i);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

class Solution:
    def minSumOfLengths(self, arr, target):
        n = len(arr)

        best = [float('inf')] * n

        map = {0: -1}

        total = 0
        ans = float('inf')
        curBest = float('inf')

        for i in range(n):
            total += arr[i]

            if total - target in map:
                j = map[total - target]
                length = i - j

                if j >= 0 and best[j] != float('inf'):
                    ans = min(ans, length + best[j])

                curBest = min(curBest, length)

            best[i] = curBest
            map[total] = i

        return -1 if ans == float('inf') else ans

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int n = arr.size();

        vector<int> best(n, INT_MAX);

        unordered_map<int, int> mp;
        mp[0] = -1;

        int sum = 0;
        int ans = INT_MAX;
        int curBest = INT_MAX;

        for (int i = 0; i < n; i++) {
            sum += arr[i];

            if (mp.count(sum - target)) {
                int j = mp[sum - target];
                int len = i - j;

                if (j >= 0 && best[j] != INT_MAX) {
                    ans = min(ans, len + best[j]);
                }

                curBest = min(curBest, len);
            }

            best[i] = curBest;
            mp[sum] = i;
        }

        return ans == INT_MAX ? -1 : ans;
    }
};

class Solution {
    minSumOfLengths(arr, target) {
        const n = arr.length;

        const best = new Array(n).fill(Infinity);

        const map = new Map();
        map.set(0, -1);

        let sum = 0;
        let ans = Infinity;
        let curBest = Infinity;

        for (let i = 0; i < n; i++) {
            sum += arr[i];

            if (map.has(sum - target)) {
                const j = map.get(sum - target);
                const len = i - j;

                if (j >= 0 && best[j] !== Infinity) {
                    ans = Math.min(ans, len + best[j]);
                }

                curBest = Math.min(curBest, len);
            }

            best[i] = curBest;
            map.set(sum, i);
        }

        return ans === Infinity ? -1 : ans;
    }
}