JAVA 15 lines solution


  • 23
    A
        public int numberOfArithmeticSlices(int[] A) {
            int re = 0;
            HashMap<Integer, Integer>[] maps = new HashMap[A.length];
            for(int i=0; i<A.length; i++) {
                maps[i] = new HashMap<>();
                int num = A[i];
                for(int j=0; j<i; j++) {
                    if((long)num-A[j]>Integer.MAX_VALUE) continue;
                    if((long)num-A[j]<Integer.MIN_VALUE) continue;
                    int diff = num - A[j];
                    int count = maps[j].getOrDefault(diff, 0);
                    maps[i].put(diff, maps[i].getOrDefault(diff,0)+count+1);
                    re += count;
                }
            }
            return re;
        }
    

  • 1
    H

    Could you give some explanation of your solution?


  • 0
    C

    Very clean and understandable! Upvote


  • 2
    C

    @haili2
    I think the idea is based on each element to cal the number of all possible differences cases.
    [2,4,6,8,10]
    Like based on 6, to calculate the difference value of 4,2,0,-2,-4, the map is
    4:1
    2:2
    so when we move to element 8, the map will be
    6:1
    4:1
    2:3


  • 3

    correct me if I'm wrong.
    I think the idea is to store the diff and number of times this diff has appeared before in a hash map for each element;
    And we only calculate the diff between current element and the element before current.
    for example:
    [2] stores a empty hashmap
    [2,4] now 4 stores a mapentry [2,1] because 4-2 = 2,and for element 2 stores nothing
    [2,4,6] 6-4 =2 and since element 4 stores[2,1], which means diff 2 has appeared once before, so count = 1 and we put [2,2] in 6. Also 6-2 = 4, we put [4,1] in 6;

    the timing of record count and pass it to the result is perfect, i wish i could work it out by myself one day

    hope it helps!


  • 0
    This post is deleted!

  • 3

    Try to make a explanation:

    Given a array [1,2,2,3,4], we want to find the number of all the unique subsequences (with at least three element) with same difference between two consecutive number in the subsequence. If we know the number of unique subsequences of array [1,2,2,3], we can find the answer to the array [1,2,2,3,4] just by finding all the valid sequences ends in number 4. This brings us the idea that this is DP Problem. So we build our answer by searching for all valid subsequence ending with each number in the array.

    But how can we find all the valid subsequences ending in number 4 for example. We search for the number that comes before 4, so we do iterate through all the number preNum before 4, take the difference diff = 4 - preNum. Then we see if we can know all the valid subsequences ending in preNum with difference diff, we say we find all the valid subsequences ending in 4 with difference diff. To maintain that information, we use HashMap for each element in the array. The key-value will be <diff, len> means the longest valid subsequence ending in this number with consecutive difference diff has length len.

    Then we traverse through all the element in the array, for all the diff, add up the number of valid subsequence, we should get the answer. But there are edge cases that should be handled with care.

    For the Example [1,2,2,3,4]. We see there are duplicate numbers and we may overwrite what we have and leave some valid answer. The map building is like

    [ 1,                 2 ,                 2,               3,                 4]
                     <1, 1>                <0, 1>         <1, 4>            <1,5>
                                            <1,1>         <2, 1>            <2,1>
                                                                            <3,1>
    

    cause we have two 2 before number 3, we have to add up the previous value if the map already have the diff key.


  • 0

    This solution remind me the HashMap solution for two sum.


Log in to reply
 

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