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

Tags: Medium Dynamic Programming

Links: https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/

---

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

Example 4:

Input: arr = [5,5,4,4,5], target = 3
Output: -1
Explanation: We cannot find a sub-array of sum = 3.

Example 5:

Input: arr = [3,1,1,1,5,1,2,1], target = 3
Output: 3
Explanation: Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.

Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 1000
• 1 <= target <= 10^8

---

class Solution {
    struct Node {
        int start, end;
        int length;
        Node(int s, int e, int l) : start(s), end(e), length(l) {}
    };

public:
    int minSumOfLengths(vector<int>& arr, int target) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = arr.size();
        vector<int> preSum(n + 1, 0);
        for (int i = 1; i <= n; ++i) preSum[i] = preSum[i - 1] + arr[i - 1];

        vector<Node> res;
        for (int i = 0; i <= n; ++i) {
            int pos = lower_bound(preSum.begin(), preSum.end(), preSum[i] + target) - preSum.begin();
            if (pos > n || preSum[pos] != preSum[i] + target) continue;
            res.push_back(Node(i, pos - 1, pos - i));
        }

        sort(res.begin(), res.end(), [] (const Node & a, const Node & b) {
            return (a.length < b.length) || (a.length == b.length && a.start < b.start);
        });

        int m = res.size(), ans = -1;
        for (int i = 0; i < m - 1; ++i) {
            for (int j = i + 1; j < m; ++j) {
                if (overlap(res[i], res[j])) continue;
                ans = res[i].length + res[j].length;
                return ans;
            }
        }

        return ans;
    }

    bool overlap(const Node & a, const Node & b)
    {
        return (b.start <= a.start && a.start <= b.end) || (b.start <= a.end && a.end <= b.end);
    }
};

题目给出的样例表明需要寻找连续的子数组，并且需要得到连续子数组的和，于是想到用前缀和来解决。因为数组内的数字都是正整数，所以前缀和是单调递增的，那么去寻找连续区间和等于目标值，我们可以使用二分的方法来进行加速查找，并将区间和等于目标值的左右端点和区间长度，存储在数组res里面。然后根据长度排序，选出不重叠的两个即可。

这种做法虽然可以通过，但是可以考虑构造这样一种样例：数组的长度$n = 10^5$，让target = n / 2，数组里的所有数字全是1，这样数组res的长度就会变成n/2，查找的过程时间复杂度是$O( \frac{n}{2} \times \frac{n}{2}) = O(n^2)$，讲道理应该是不可以通过才对，应该是测试用例里面没有这种情况。

另外在查找区间和是否等于target的部分，可以利用unordered_map来进行优化，实现$O(1)$的查找。