Check Subarray Sum
Given an array of integers and an integer k, determine whether there are two non-overlapping subarrays of the same length which have a sum equals to k. Return a Boolean value true if such subarrays exist, otherwise return false.
[ [ 1, 2, 3, 5, 2, 3, 1 ], 8 ]
Explanation. There are two subarrays with length 3 each (`[1, 2, 3]`, one starting at index 0 and one starting at index 4), both having a sum of 6, and `6` is not equal to `k=8`. Thus, even though there are same sum subarrays, neither matches `k` exactly.
[ [ 4, 2, 1, 3, 9, 2, 11, 5, 6 ], 16 ]
Explanation. There are two subarrays with length 3 each (`[9, 2, 11]`, one starting at index 4 and `[5, 6, 2]`, one starting after some gaps at index 7), both having a sum of 16, which is exactly `k`. Thus returns `true`.
[ [ 5, 5, 5, 5 ], 5 ]
Explanation. Although there are subarrays with sum equal to 5, there are no two non-overlapping subarrays that can be formed under the constraints of having the same length. Thus, the answer is `false`.
[ [ 1, 2, 1, 2, 1, 3 ], 3 ]
Explanation. Non-overlapping subarrays `[1, 2]` and `[2, 1]` exist and sum to `k=3`. Thus, the answer is `true`.
[ [ 1, 2 ], 5 ]
Explanation. The length of array is 2 which doesn’t allow forming two non-overlapping subarrays of the same length with the k value. Thus returns `false`.
Follow-up: Can you do this problem in less than O(n^2) time complexity?
1. The array length will be at least 1.\n2. All integers will be within the signed 32-bit integer range.\n3. The value of `k` will not exceed the sum of any possible subarray sum.
- Views
- 3