It can be done in O(n) as well:
First, create an auxilary array that sums each prefix of the array:
sums[i] = arr[0] + arr[1] + ... + arr[i]
The above can be computed in O(n) time.
Next, create a hash map Map<Integer,List<Integer>>, where the key is representing a prefix sum, and the value is a list of indices with this prefix sum. Pseudo code:
Map<Integer,List<Integer>> map = new HashMap<>();
for (int i = 0; i < sums.length; i++) {
List<Integer> l = map.get(sums[i]);
if (l == null) {
l = new ArrayList<>();
map.put(sums[i],l);
}
l.add(i);
}
Now, iterate the sums array, and for each element x, check if the map contains a key k such that x-k == S.
This is done by checking if it has a key k = S-x, which is O(1) in a hash map.
If there is such a key, then get the last index in the values list, which is also done in O(1), and take it as a candidate match.
Pseudo code:
int currentMaxLength = Integer.MIN_VALUE;
for (int i = 0; i < sums.length; i++) {
int k = S-sums[i];
List<Integer> l = map.get(k);
if (l == null) continue;
int width = Math.abs(l.getLast() - i);
if (width > currentMaxLength) currentMaxLength = width;
}
return currentMaxLength;
The idea is, if you have multiple matches for some x1,x2 such that x2-x1 = S, and where x1,x2 are prefix sums, the candidates for longest subarray are the first place where x1 appears, and the last place where x2 appears.
For x1, this is the element which i refers to in the main loop, and it is always regarded as a candidate.
For x2, you will always check the last occurance of x2, and thus it's correct.
Quicknote: The actual code also needs to regard sums[-1] = 0.
Java code:
public static int solution(int[] arr, int S) {
int[] sums = new int[arr.length+1];
int sum = 0;
//generate the sums array:
sums[0] = 0;
for (int i = 0; i < arr.length; i++) sums[i+1] = sum = sum+arr[i];
//generate map:
Map<Integer,List<Integer>> map = new HashMap<>();
for (int i = 0; i < sums.length; i++) {
List<Integer> l = map.get(sums[i]);
if (l == null) {
l = new ArrayList<>();
map.put(sums[i],l);
}
l.add(i);
}
//find longest:
int currentMaxLength = Integer.MIN_VALUE;
for (int i = 0; i < sums.length; i++) {
int k = S - sums[i];
List<Integer> l = map.get(k);
if (l == null) continue;
int width = Math.abs(l.get(l.size()-1) - i);
if (width > currentMaxLength) currentMaxLength = width;
}
return currentMaxLength;
}
public static void main(String[] args) {
System.out.println(solution(new int[] { 1, 0, -1, 1, 1, -1, -1 }, 2));
}
