O(n^2) Java + short explanation


  • 0
    A

    The idea is to store for each position i all the differences and lengths of subsequence with that difference till this position ( A[i]-A[j]). It means for how many subsequences the number on position i can be the tail. The quantity of this tails will be the answer.

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            HashMap<Integer,Integer> d[] = new HashMap[A.length];
            int ans = 0;
            for (int i=0; i<A.length; i++) {
                d[i] = new HashMap<>();
                for (int j=0; j<i; j++) {
                    long dif = (long)A[i]-A[j];
                    if (dif <= Integer.MIN_VALUE || dif > Integer.MAX_VALUE) continue;
                    int v1 = d[j].getOrDefault((int)dif,0);
                    int v2 = d[i].getOrDefault((int)dif,0);
                    ans+=v1;
                    d[i].put((int)dif, v1 + v2 + 1);
                }
            }
            return ans;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.