413. Arithmetic Slices

DP문제인데 DP테이블까지 만들건없고 변수 두개로 가능하다.

DP

길이 3이상의 등차수열(?)의 갯수를 알아내야하는 문제이다.

예외처리로 숫자가 3개가 안되면 바로 0으로 끝내버리고 시작함

3개가 기준이니까 한개전꺼랑 두개전꺼를 보면서 확인하고, 맞다고 확인하면 count를 증가시키고 정답에 count를 추가한다.
이 카운트는 현재 수열이 허용됨으로서 증가하는 길이 3이상의 수열의 갯수이다.
정답은 3이상의 누적수열 개수이다.

예를들어,

• [1,2,3]이 수열이 맞으니까 cnt=1
• [1,2,3,4]에서 2,3,4도 수열이고 1,2,3,4도 수열이다. 저장된 cnt값을 하나 증가시켜서 cnt=2가 되고, 이 cnt를 정답에 추가한다.

왜냐하면 수열 길이가 1씩 증가될수록 3개짜리 수열의 증가값도 1씩 증가하기 때문이다.

[1,2,3]은 길이 3이상 수열이 1개(1추가),
[1,2,3,4]는 길이 3이상 수열이 3개(2추가),
[1,2,3,4,5]는 길이 3이상 수열이 6개(3추가)... 이런식이다.

var numberOfArithmeticSlices = function(nums) {
    if(nums.length < 3) return 0;
    
    let ans = 0;
    
	for (let i = 2, cnt = 0; i < nums.length; i++){
        if(nums[i] - nums[i-1] === nums[i-1] - nums[i-2]){
            cnt++;
            ans+=cnt;
        }else cnt=0;
    }
		
	return ans;
};

Time, space complexity

nums 어레이 한번순회하고 변수만으로 가능하므로 시간 O(N), 공간 O(1)