So let’s describe this problem in more detail. Find a subarray whose sum is the given value in an array of all positive integers, and give the subarray’s starting subindex (closed interval), as an example:
In the array [3, 2, 1, 2, 3, 4,5], the subarray that sums to 10 is [1, 2, 3, 4], so the answer should be [2,5]. The subarray of sum 15 is [1, 2, 3, 4, 5], and the answer is [2,6].
That’s a very interesting question. Why do you say that? The simplest solutions require basic programming knowledge, and the better ones require data structures and algorithmic skills. The more efficient the solution, the more clever it is. You may not be able to think of all of them at once, but I’m sure you’ll be amazed by the magic of algorithms after reading this blog.
Back to this problem, in fact, it has O(n^3), O(n^2), O(nlogn), O(n) 4 time complexity solutions, if the difference in space complexity is counted, a total of 5 solutions, I think it is more able to observe the level of a person’s algorithm. Now let me lead you from simple to difficult five solutions from bronze to king, with you to beat the interviewer.
Here we’ll set the input parameters to (arr[],target), and I’ll use s and e for the start and end positions in the rest of the code. In addition, to simplify code thinking, we will assume that there is at most one solution in a given parameter. (In fact, multiple solutions are not difficult, but can make the code longer, which is not good for describing ideas. Multiple solutions will be left for your homework.)
Bronze – Violent solution
First, of course, is the simplest violence solution, which is to iterate over the starting position S and the ending position E, and then find the sum of all the numbers between s and E. The three-layer loop is simple and does not require any skill. You can solve it when you learn programming in the first year.
public int[] find(int[] arr, int target) {
for (int s = 0; s < arr.length; s++) {
for (int e = s+1; e < arr.length; e++) {
int sum = 0;
for (int k = s; k <= e; k++) { // Find the sum between s and e
sum += arr[k];
}
if (target == sum) {
return new int[]{s, e}; }}}return null;
}
Copy the codeSo let’s analyze the time complexity, which is obviously O(n^3), and when n goes over 1000 it’s visually slow, so how do you optimize it?
Silver – Space for time
Sum [1,10] = sum[2,10] = sum[2,10] = sum[2,10] = sum[2,10] Can we eliminate this part of the repeat scan? So this is where we have to do a neat transformation.
Sum [s, e] = sum[0, e] -sum [0, s-1], sum[0, I] In fact, the sum array can be obtained through a data preprocessing. In the figure above, the sum of the blue region of ARR is exactly equal to the red minus the green in the sum array, i.e., sum(arr[3]-arr[7]) = sum[7]-sum[2].
Back to the code, I use an extra array arrSum to store all sums between 0 and I (0<= I <n). SumArr subscript starts at 1 for processing convenience. SumArr [I] represents sum[0, i-1] in the remote array. With sumArr, sum[s,e] can be obtained indirectly by sumArr[e+1] -sumarr [s]. The complete code is as follows:
public int[] find(int[] arr, int target) {
int[] sumArr = new int[arr.length + 1];
for (int i = 1; i < sumArr.length; i++) {
sumArr[i] = sumArr[i-1] + arr[i-1]; // Preprocess to get the accumulative array
}
for (int s = 0; s < arr.length; s++) {
for (int e = s+1; e < arr.length; e++) {
if (target == sumArr[e+1] - sumArr[s]) {
return new int[]{s, e}; }}}return null;
}
Copy the codeBy swapping space for time, we can directly reduce the time complexity from O(n^3) to O(n^2).
Gold – Binary search
Careful you may have found that, because the arR given are all positive integers, so sumArr must be increasing and ordered, for ordered arrays, we can directly use binary search. If e of s exists, then sumArr[e] must be equal to sumArr[s] + target. The modified code is as follows. Compared with the code above, binary search is added.
public int[] find(int[] arr, int target) {
int[] sumArr = new int[arr.length + 1];
for (int i = 1; i < sumArr.length; i++) {
sumArr[i] = sumArr[i-1] + arr[i-1];
}
for (int s = 0; s < arr.length; s++) {
int e = bSearch(sumArr, sumArr[s] + target);
if(e ! = -1) {
return new int[]{s, e}; }}return null;
}
// Binary search
int bSearch(int[] arr, int target) {
int l = 1, r = arr.length-1;
while (l < r) {
int mid = (l + r) >> 1;
if (arr[mid] >= target) {
r = mid;
} else {
l = mid + 1; }}if(arr[l] ! = target) {return -1;
}
return l - 1;
}
Copy the codeFrom this, we continue to reduce the temporal complexity from O(n^2) to O(nlogn).
Diamond-hashmap optimization
In addition to binary optimization, the lookup of ordered arrays can also be optimized using hashMap, with the query time complexity of hashMap O(1). Once again, we trade space for time.
public int[] find(int[] arr, int target) {
int[] sumArr = new int[arr.length + 1];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 1; i < sumArr.length; i++) {
sumArr[i] = sumArr[i-1] + arr[i-1];
map.put(sumArr[i], i-1);
}
for (int s = 0; s < arr.length; s++) {
int e = map.getOrDefault(sumArr[s]+target, -1);
if(e ! = -1) {
return new int[]{s, e}; }}return null;
}
Copy the codeWe finally reduced the time complexity to O(n), which was a quantum leap.
King – ruler method
Don’t worry, we’re not done yet. There’s a king’s solution to this problem. Above, we reduced the time complexity step by step from O(n^3) through continuous optimization, but we increased the use of storage step by step. From the newly added sumArr numbers at the beginning to the HashMap at the end, the space complexity changed from O(1) to O(n). Is there a way to reduce the space complexity as well? I can write about that there must be.
This algorithm is called the ruler method. Ruler method, the name is a little hard to understand. So let’s just take a concrete example, let’s say you have strings of different lengths in n tones sitting side by side, and you want to take the contiguous part of them and make a string of length target, which is contiguous. If it’s too short, put another string behind it. If it’s too long, throw the top one away until it’s just the right length.
We don’t need this ruler in use, just use Target as ruler. As an example, the following figure shows how to find a subarray of sum 22 from an array.
Why is the ruler method correct? I understand that the ruler method is actually an optimization of the two-silver solution, which traverses the starting point S, but does not do invalid traversal of the end point E. If E reaches a certain position and has exceeded, because the array is full of positive numbers, it must be exceeded after that, there is no need to continue traversing E. If s moves to the right and the sum is smaller, then the sum will be smaller and there is no need to adjust S further… The whole process is like fixing S to traverse E, then fixing E to traverse S… Until you get the result.
The base of the rule of thumb is that if you move e to the right the sum must be increasing, and if you move S to the right the sum must be decreasing, which means that all the numbers in the array must be positive. No perfect algorithm can solve any problem, but there must be a perfect solution for a particular problem.
After finishing the ruler method, let’s see how to solve this problem with the ruler method, the code is relatively simple, as follows:
public int[] find(int[] arr, int target) {
int s = 0, e = 0;
int sum = arr[0];
while (e < arr.length) {
if (sum > target) {
sum -= arr[s++];
} else if (sum < target) {
sum += arr[++e];
} else {
return new int[]{s, e}; }}return null;
}
Copy the codeThere’s only one loop, O(n). There’s no extra space, order one, and that’s the perfect solution.
conclusion
This algorithm looks simple at first glance, but it is not simple at first glance. You may come across an interview and not be able to come up with an optimal solution, but a workable solution is better than no solution at all. When I asked someone this question in the interview before, he just thought about how to solve it best, but didn’t even write out the simplest bronze solution. Remember that the next interview, really can not solve the answer to give 60 points, and then try to improve the score, do not hand in blank paper. To give a feasible solution and then continue iterative optimization, I think this is also a good idea to solve a complex problem.
No one is born a king, only constant efforts to become a king.
Welcome on my interview column senior program apes this topic selection, continuously updated, permanent free, this column will continue to include apes classic interview questions I met senior program, in addition to providing detailed their thinking, will also provide extension, from the perspective of the interviewer is the default choice of people’s interview is advanced, the hope can help you find a better job. In addition, also soliciting interview questions, if you encounter the question can not tell me in private, valuable questions I will give you a blog.