Share my super easy solution O(n) time and O(1) space


  • 0
    U

    The idea is pretty simple think about 1,2,3,4,5...,

    if we stop at 3 we have 1 option;
    if we stop at 4 we have 3 options;
    if we stop at 5 we have 5 option;
    .
    .
    .

    so if we know how many options we have now and how many options we have before: we can have this simple formula:

    next = current*2 + 1 - previous;

    The reason is pretty straightforward, thinking about from 3->4 -> 5:
    At 3 we have 1,2,3
    At 4 we have 1,2,3 | 2,3,4 | 1,2,3,4
    At 5 we have 1,2,3 | 2,3,4 | 3,4,5 | 1,2,3,4 | 2,3,4,5 | 1,2,3,4,5

    if we want to calculate how many options we have at 5, we know 1,2,3,4 have 3 options and 2,3,4,5 also have 3 options and 1,2,3,4,5, so now we have 7 options but we have a overlap 2,3,4 so we need to minus the overlap, which equals how many options we have at 3.

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            int len = A.length;
            if(len < 3) return 0;
            
            int diff = A[1] - A[0];
            int curDiff;
            
            int result = 0;
            int current = 0;
            int prev = 0;
            for(int i = 2 ; i < len ; i++){
                curDiff = A[i] - A[i-1];
                if(curDiff == diff){
                    if(current == 0) current = 1;
                    else{
                        int temp = current;
                        current = current*2+1-prev;
                        prev = temp;
                    }
                }else{
                    diff = curDiff;
                    result += current;
                    current = 0;
                }
            }
            
            result += current;
            return result;
        }
    }
    

Log in to reply
 

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