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

Description

You are given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with a 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.

 

Constraints:

• 1 <= arr.length <= 105
• 1 <= arr[i] <= 1000
• 1 <= target <= 108

 

Solutions

Solution: Sliding Window

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
const minSumOfLengths = function (arr, target) {
  const minSumLength = [];
  let left = 0;
  let currentSum = 0;
  let result = Number.MAX_SAFE_INTEGER;
  let minSize = Number.MAX_SAFE_INTEGER;

  for (let index = 0; index < arr.length; index++) {
    currentSum += arr[index];

    while (currentSum > target) {
      currentSum -= arr[left];
      left += 1;
    }
    if (currentSum === target) {
      const size = index - left + 1;

      if (minSumLength[left - 1]) {
        result = Math.min(result, size + minSumLength[left - 1]);
      }
      minSize = Math.min(size, minSize);
    }
    minSumLength[index] = minSize;
  }
  return result === Number.MAX_SAFE_INTEGER ? -1 : result;
};