Skip to content

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

Approach 1: HashTable

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int minSumOfLengths(vector<int>& arr, int target) {
    int ans = INT_MAX;
    int leftLength = INT_MAX;
    int prefix = 0;
    unordered_map<int, int> prefixToIndex{{0, -1}};

    for (int i = 0; i < arr.size(); ++i) {
      prefix += arr[i];
      prefixToIndex[prefix] = i;
    }

    prefix = 0;

    for (int i = 0; i < arr.size(); ++i) {
      prefix += arr[i];
      if (const auto it = prefixToIndex.find(prefix - target);
          it != prefixToIndex.cend())
        leftLength = min(leftLength, i - it->second);
      if (leftLength < INT_MAX)
        if (const auto it = prefixToIndex.find(prefix + target);
            it != prefixToIndex.cend())
          ans = min(ans, leftLength + it->second - i);
    }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public int minSumOfLengths(int[] arr, int target) {
    int ans = Integer.MAX_VALUE;
    int leftLength = Integer.MAX_VALUE;
    int prefix = 0;
    Map<Integer, Integer> prefixToIndex = new HashMap<>();
    prefixToIndex.put(0, -1);

    for (int i = 0; i < arr.length; ++i) {
      prefix += arr[i];
      prefixToIndex.put(prefix, i);
    }

    prefix = 0;

    for (int i = 0; i < arr.length; ++i) {
      prefix += arr[i];
      if (prefixToIndex.containsKey(prefix - target))
        leftLength = Math.min(leftLength, i - prefixToIndex.get(prefix - target));
      if (leftLength < Integer.MAX_VALUE)
        if (prefixToIndex.containsKey(prefix + target))
          ans = Math.min(ans, leftLength + prefixToIndex.get(prefix + target) - i);
    }

    return ans == Integer.MAX_VALUE ? -1 : ans;
  }
}

Approach 2: Sliding Window

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int minSumOfLengths(vector<int>& arr, int target) {
    int ans = INT_MAX;
    int sum = 0;  // the window sum
    // best[i] := the minimum length of subarrays in arr[0..i] that have
    // sum = target
    vector<int> best(arr.size(), INT_MAX);

    for (int l = 0, r = 0; r < arr.size(); ++r) {
      sum += arr[r];  // Expand the window.
      while (sum > target)
        sum -= arr[l++];  // Shrink the window.
      if (sum == target) {
        if (l > 0 && best[l - 1] != INT_MAX)
          ans = min(ans, best[l - 1] + r - l + 1);
        best[r] = min(best[r], r - l + 1);
      }
      if (r > 0)
        best[r] = min(best[r], best[r - 1]);
    }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int minSumOfLengths(int[] arr, int target) {
    int ans = Integer.MAX_VALUE;
    int sum = 0; // the window sum
    // best[i] := the minimum length of subarrays in arr[0..i] that have
    // sum = target
    int[] best = new int[arr.length];
    Arrays.fill(best, Integer.MAX_VALUE);

    for (int l = 0, r = 0; r < arr.length; ++r) {
      sum += arr[r]; // Expand the window.
      while (sum > target)
        sum -= arr[l++]; // Shrink the window.
      if (sum == target) {
        if (l > 0 && best[l - 1] != Integer.MAX_VALUE)
          ans = Math.min(ans, best[l - 1] + r - l + 1);
        best[r] = Math.min(best[r], r - l + 1);
      }
      if (r > 0)
        best[r] = Math.min(best[r], best[r - 1]);
    }

    return ans == Integer.MAX_VALUE ? -1 : ans;
  }
}