[JS] Arithmetic Slices

🔒 문제 (LeetCode 413)

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

• For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.

Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

Constraints:

• 1 <= nums.length <= 5000
• -1000 <= nums[i] <= 1000

 

🌊 입출력

Example 1:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2:

Input: nums = [1]
Output: 0

 

---

 

🔑 해결

🌌 알고리즘 - DP

arithmetic sequence = 등차수열

주어진 배열에서 연속된 순서를 바꾸지 않고 만들 수 있는 요소 3개 이상의 subarray 중 등차수열이 되는 개수를 찾는 문제

dp 배열에 i번째 요소까지 포함하여 만들 수 있는 새로운 등차수열의 개수를 저장한다.

현재 요소를 i라고 할 때 [i-2, i-1, i] 가 등차수열일 경우 [i-3, i-2, i-1] + [i] 도 등차수열이기 때문에

dp[i] = dp[i-1] + 1 이고 dp 배열의 모든 수의 합이 만들 수 있는 subarray의 총 개수가 된다.

Ex) nums = [1, 2, 3, 4]
dp[0] = 0,.dp[1] = 0
d[2] = 1 : [1, 2, 3]
dp[3] = dp[2] + 1 : [2, 3, 4] + [1, 2, 3, 4] 

/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
    let sum = 0
    let dp = new Array(nums.length).fill(0)
    
    for(let i = 2; i < nums.length; i++) {
        if(nums[i] - nums[i-1] === nums[i-1] - nums[i-2]) {
            dp[i] = dp[i-1] + 1
            sum += dp[i]
        }
    }
    return sum
};