[Leetcode] 413. Arithmetic Slices

문제 : https://leetcode.com/problems/arithmetic-slices/

---

nums 배열을 탐색하면서 탐색 중인 nums[i] 를 포함하는 정답가능한 subarrays 수를 정답에 더해나간다.

nums[i]를 포함하는 정답가능한 subarrays 수를 구하기 위해, nums[i], nums[i-1] 두 요소간 차이와 동일한 nums 요소 수를 cnt 변수에 저장한다. nums[i]-nums[i-1]이 nums[i-1]-nums[i-2] 와 동일하다면 cnt + 1, 동일하지 않다면 cnt를 2(i-1, i)로 갱신한다. 

nums[i]를 포함하는 정답가능한 subarrays 수는 cnt-2이다. 정답가능 하위배열은 앞에서부터 요소를 하나씩 삭제해가며 최소 3개이상의 요소만 있으면 정답배열이 될 수 있기 때문이다.

예를들어, 동일한 요소차이를 가지는 최대길이 하위배열이 [2,3,4,5]라면 마지막 요소인 5를 포함하는 정답가능 하위배열은 [2,3,4,5], [3,4,5] 2개이다.

 

시간복잡도는 N = |nums| 일 때, O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/413.%20Arithmetic%20Slices.cpp