Problem statement

https://binarysearch.com/problems/Two-Non-Overlapping-Lists-With-Target-Sums/

Solution

First, find all intervals with sum k, using cumulative sums. It can be shown that there will be not more than n of them: indeed for each end if we have two intervals, they will be overlapping. Then we use problem BinarySearch 0655 Minimum Size of Two Non-Overlapping Intervals to shortest sum of two non-overlapping intervals.

Complexity

It is O(n log n) for time and space. In fact it can be made O(n), because when we create I we can make it already sorted (now it is sorted by ends, if we reverse array)

Code

class Solution:
    def solve(self, nums, k):
        d, I = {0: -1}, []
        for i, x in enumerate(accumulate(nums)):
            if x - k in d:
                I += [[d[x - k] + 1, i]]
            d[x] = i

        if len(I) <= 1: return -1
        
        I = sorted(I)
        acc = list(accumulate([y - x for x, y in I[::-1]], min))[::-1]
        ans = float("inf")
        for x, y in I:
            idx = bisect.bisect(I, [y, float("inf")])  
            if idx < len(I):
                ans = min(ans, y - x + 1 + acc[idx] + 1)

        return ans if ans != float("inf") else -1