Given an array nums and a target value k, find the maximum length of a Contiguous subarray that sums to k. If there isn’t one, return 0 instead. The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
Example 1:
Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.Example 2:
Input: nums = [-2, -1, 2, 1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.
Bruteforce Algorithm to Find Maximum Size SubArray with a Given Sum
The first idea has to be the bruteforce: checking each possible pair of sub arrays with O(N^2), then compute the sum with another O(N) loop, the overall the complexity of the intuitive bruteforce algorithm takes O(N^3) to compute – which is very very slow given the size of the input may be larger than 10K. The space complexity is O(1) for this straightforward implementation.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public: int maxSubArrayLen(vector<int>& nums, int k) { int n = nums.size(), r = 0; for (int i = 0; i < n; ++ i) { for (int j = i; j < n; ++ j) { int sum = 0; for (int a = i; a <= j; ++ a) { // subarray sum sum += nums[a]; } if (sum == k) { // find a match, record the max size r = max(r, j - i + 1); } } } return r; } }; |
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int n = nums.size(), r = 0;
for (int i = 0; i < n; ++ i) {
for (int j = i; j < n; ++ j) {
int sum = 0;
for (int a = i; a <= j; ++ a) { // subarray sum
sum += nums[a];
}
if (sum == k) { // find a match, record the max size
r = max(r, j - i + 1);
}
}
}
return r;
}
};Maximum Size Subarray of Sum using Improved Bruteforce Algorithm
Can we do better? At each iteration, we move either one position of left cursor or we move left one position of right cursor, then the current sum can be updated accordingly. Thus, the following bruteforce algorithm is improved and the speed efficiency is reduced to O(N^2), the space complexity is O(1) constant.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public: int maxSubArrayLen(vector<int>& nums, int k) { int64_t ans = 0; int64_t sum = 0; for (int i = 0; i < nums.size(); ++ i) { sum += nums[i]; } if (sum == k) return nums.size(); int64_t sum1 = sum; for (int i = 0; i < nums.size(); ++ i) { sum1 -= ((i > 0) ? nums[i - 1] : 0); // clear the left-most value int sum2 = sum1; for (int j = nums.size() - 1; j >= i; -- j) { sum2 -= (j == nums.size() - 1) ? 0 : nums[j + 1]; // clear the right-most value if (sum2 == k) { int x = j - i + 1; if (x > ans) ans = x; } } } return ans; } }; |
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int64_t ans = 0;
int64_t sum = 0;
for (int i = 0; i < nums.size(); ++ i) {
sum += nums[i];
}
if (sum == k) return nums.size();
int64_t sum1 = sum;
for (int i = 0; i < nums.size(); ++ i) {
sum1 -= ((i > 0) ? nums[i - 1] : 0); // clear the left-most value
int sum2 = sum1;
for (int j = nums.size() - 1; j >= i; -- j) {
sum2 -= (j == nums.size() - 1) ? 0 : nums[j + 1]; // clear the right-most value
if (sum2 == k) {
int x = j - i + 1;
if (x > ans) ans = x;
}
}
}
return ans;
}
};We can, also pre-compute the left and right sum array, and use the total sum minus these two to compute the subarray sum. The following improved bruteforce algorithm still checks O(N^2) pairs, however, it uses pre-computed left and right sum to construct the subarray sum in the middle range.
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 30 | class Solution { public: int maxSubArrayLen(vector<int>& nums, int k) { int n = nums.size(), r = 0; if (n == 0) return 0; vector<int> left(n, 0); vector<int> right(n, 0); int total = 0; for (int i = 1; i < n; ++ i) { total += nums[i - 1]; left[i] = total; } total += nums[n - 1]; int total2 = 0; for (int j = n - 2; j >= 0; --j) { total2 += nums[j + 1]; right[j] = total2; } for (int i = 0; i < n; ++ i) { for (int j = i; j < n; ++ j) { // left and right range sum exclusive int sum = total - left[i] - right[j]; if (sum == k) { r = max(r, j - i + 1); } } } return r; } }; |
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int n = nums.size(), r = 0;
if (n == 0) return 0;
vector<int> left(n, 0);
vector<int> right(n, 0);
int total = 0;
for (int i = 1; i < n; ++ i) {
total += nums[i - 1];
left[i] = total;
}
total += nums[n - 1];
int total2 = 0;
for (int j = n - 2; j >= 0; --j) {
total2 += nums[j + 1];
right[j] = total2;
}
for (int i = 0; i < n; ++ i) {
for (int j = i; j < n; ++ j) {
// left and right range sum exclusive
int sum = total - left[i] - right[j];
if (sum == k) {
r = max(r, j - i + 1);
}
}
}
return r;
}
};The space complexity is O(N). We can, however, compute the sum on the fly, which seems the most efficient bruteforce algorithms.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public: int maxSubArrayLen(vector<int>& nums, int k) { int n = nums.size(), r = 0; for (int i = 0; i < n; ++ i) { int sum = 0; // reset the sum for (int j = i; j < n; ++ j) { sum += nums[j]; // compute the sum on the fly if (sum == k) { // find a match, record the max size r = max(r, j - i + 1); } } } return r; } }; |
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int n = nums.size(), r = 0;
for (int i = 0; i < n; ++ i) {
int sum = 0; // reset the sum
for (int j = i; j < n; ++ j) {
sum += nums[j]; // compute the sum on the fly
if (sum == k) { // find a match, record the max size
r = max(r, j - i + 1);
}
}
}
return r;
}
};The still takes O(N^2) and it requires O(1) constant space.
Finding Maximum Size SubArray Sum using Prefix with Hashmap
A better algorithm is to use hashmap to store the prefix sum and as a result, the following algorithm runs at linear time O(N) and it is a lot faster 30 to 50 times faster than the above bruteforce algorithms.
As we are going through the numbers one by one in the array, we update the prefix sum and store the sum as key – index as value in the hashmap (only if the key does not exist, as we are looking for the longest subarray size). If at any time, we find that the prefix with key/sum (current sum minus target) exists in the hashmap O(1) lookup by the way, we retrieve the index, and the length of the subarray would be the current index minus the prefix index.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public: int maxSubArrayLen(vector<int>& nums, int k) { int n = nums.size(), r = 0; unordered_map<int, int> prefix; int total = 0; prefix[0] = -1; // as index starts from zero for (int i = 0; i < nums.size(); ++ i) { total += nums[i]; if (prefix.find(total) == prefix.end()) { prefix[total] = i; } if (prefix.find(total - k) != prefix.end()) { r = max(r, i - prefix[total - k]); } } return r; } }; |
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int n = nums.size(), r = 0;
unordered_map<int, int> prefix;
int total = 0;
prefix[0] = -1; // as index starts from zero
for (int i = 0; i < nums.size(); ++ i) {
total += nums[i];
if (prefix.find(total) == prefix.end()) {
prefix[total] = i;
}
if (prefix.find(total - k) != prefix.end()) {
r = max(r, i - prefix[total - k]);
}
}
return r;
}
};The prefix[0] will be set to minus one, as the index of the array starts at zero – the length is plus one to the index difference. The time and space complexity is both O(N).
After studying these algorithms/approaches, how about solving a similar problem of Algorithms to Count Subarray (Contiguous) Sum That Equals k?
If the array only contains zeros and ones, and we want to find out the longest balanced subarray with equal numbers of 1’s and 0’s, we can still use the algorithms here: The Contiguous Binary Array with Equal Numbers of Ones and Zeros
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: WordPress Hosting Services You Can't DIY
Next Post: Using BackTracking Algorithm to Find the Combination Integer Sum