My idea is to subtract 1 from all the elements. Then in order for a subarray of numbers to satisfy the conditions, the numbers in the subarray have to sum to 0, since there are l-r+1 elements between l and r. So I made a prefix sum array for the numbers after subtracting 1 from all the elements, but that didn’t work. Where did I go wrong?
import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;
public class GoodSubarrays {
public static void main(String args[]) {
Kattio io = new Kattio();
int numCases = io.nextInt();
for (int c = 0; c<numCases; c++) {
int arraySize = io.nextInt();
long[] nums = new long[arraySize];
String sequence = io.next();
long total = 0;
for (int i = 0; i<sequence.length(); i++) {
nums[i] = Long.valueOf("" + sequence.charAt(i))-(long)1;
if (nums[i] == 0) {
total++;
}
}
HashMap<Long, Long> valueCounts = new HashMap<>(); //value, count
for (int i = 1; i<nums.length; i++) {
nums[i] = nums[i] + nums[i-1];
if (nums[i] == 0 && i!=0) {
total++;
}
if (valueCounts.containsKey(nums[i])) {
valueCounts.put(nums[i], valueCounts.get(nums[i])+1);
}
else {
valueCounts.put(nums[i], (long)1);
}
}
//A - B = 0
for (Long i : valueCounts.keySet()) {
total += valueCounts.get(i)*(valueCounts.get(i)-1)/2;
}
io.println(total);
}
io.close();
}
static class Kattio extends PrintWriter {
private BufferedReader r;
private StringTokenizer st;
// standard input
public Kattio() { this(System.in, System.out); }
public Kattio(InputStream i, OutputStream o) {
super(o);
r = new BufferedReader(new InputStreamReader(i));
}
// USACO-style file input
public Kattio(String problemName) throws IOException {
super(problemName + ".out");
r = new BufferedReader(new FileReader(problemName + ".in"));
}
// returns null if no more input
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(r.readLine());
return st.nextToken();
} catch (Exception e) { }
return null;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
}
}