[leetCode/JS] 446. Arithmetic Slices II - Subsequence

문제 설명

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

A sequence of numbers 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.
• For example, [1, 1, 2, 5, 7] is not an arithmetic sequence.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

• For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

The test cases are generated so that the answer fits in 32-bit integer.

입출력 예

Example 1:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

Example 2:

Input: nums = [7,7,7,7,7]
Output: 16
Explanation: Any subsequence of this array is arithmetic.

Constraints

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

 

 

---

 

 

내 솔루션

/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
  const cache = Array.from(Array(nums.length), () => new Map())
  let answer = 0;
  for(let i = 0; i < nums.length; i++) {
    for(let j = 0; j < i; j++) {
      let cache_i = cache[i].get(nums[i]-nums[j]) || 0;
      let cache_j = cache[j].get(nums[i]-nums[j]) || 0;
      cache[i].set(nums[i]-nums[j], cache_i + cache_j + 1)
      answer += cache_j;
    }
  }
  return answer
};

--------------
nums[1] - nums[0] 4 2 2
cache_i: 0, cache_j: 0, i+j+1: 1
--------------
nums[2] - nums[0] 6 2 4
cache_i: 0, cache_j: 0, i+j+1: 1
nums[2] - nums[1] 6 4 2
cache_i: 0, cache_j: 1, i+j+1: 2
--------------
nums[3] - nums[0] 8 2 6
cache_i: 0, cache_j: 0, i+j+1: 1
nums[3] - nums[1] 8 4 4
cache_i: 0, cache_j: 0, i+j+1: 1
nums[3] - nums[2] 8 6 2
cache_i: 0, cache_j: 2, i+j+1: 3
--------------
nums[4] - nums[0] 10 2 8
cache_i: 0, cache_j: 0, i+j+1: 1
nums[4] - nums[1] 10 4 6
cache_i: 0, cache_j: 0, i+j+1: 1
nums[4] - nums[2] 10 6 4
cache_i: 0, cache_j: 1, i+j+1: 2
nums[4] - nums[3] 10 8 2
cache_i: 0, cache_j: 3, i+j+1: 4
--------------
// cache
[
  Map(0) {},
  Map(1) { 2 => 1 },
  Map(2) { 4 => 1, 2 => 2 },
  Map(3) { 6 => 1, 4 => 1, 2 => 3 },
  Map(4) { 8 => 1, 6 => 1, 4 => 2, 2 => 4 }
]

 

감상평

• 아니 너무 한거 아니요?
• 일요일 한시간 그냥 날렸네