• + 6 comments

    So, your answer is not really O(n^2), but rather O(n*m), since your sum() method iterates over m elements in the array for every n element in the array. Thus, O(m*n).

    You can improve though, if you figure out a smarter way to keep track of the sum of the m previous pieces. You can for example just hold a sum variable where you remove the last element and add the new one as you iterate, instead of calculating the whole sum each and every time. (Imagine the repeated work when your m grows).

    Here is a java example:

    static int solve(int n, int[] s, int d, int m){
        int sum = 0;
        int r = 0;
        for (int i = 0; i < s.length; i++) {
            sum += s[i];
            // M is never less than 1
            if (i > m - 1) sum -= s[i - m];
            if (i >= m - 1 && sum == d) r++;
        }
        return r;
    }