446. Arithmetic Slices II - Subsequence

Problem

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&nbsp; <= nums.length <= 1000

• -2^31 <= nums[i] <= 2^31 - 1

Solution(Java)

class Solution {
    public int numberOfArithmeticSlices(int[] nums)
    {
        HashMap<Integer , Integer> maps[] = new HashMap[nums.length]; // creating array of hashmaps 
        // HashMap contains :
        // 1.) common-diff / cd : common diff btw nums[i] & nums[j] ( where, j E [0 , i-1])
        // 2.) count : count of APs(min size = 2) that end with ith element and has a common-diff of maps[i].cd
        for(int i = 0;i<nums.length;i++)
        {
            maps[i] = new HashMap<>();
        }

        int ans = 0; // keeps count of no. of APs that are of min length 3 

        for(int i = 0 ;i<nums.length;i++)
        {
            for(int j = 0 ; j < i ; j++)
            {
                long cd = (long)nums[i] - (long)nums[j]; // diff btw ith & jth element

                if(cd <= Integer.MIN_VALUE || cd >= Integer.MAX_VALUE)
                {
                    continue;
                }
                int countAPj = 0; // count of APs that end with nums[j] and have common-diff = cd
                int countAPi = 0; // count of APs that end with nums[i] and have common-diff = cd

                // If the jth map contains AP ending with nums[j] & comm-diff = cd , 
                //that means we can add nums[i] next to it and hence further extend that AP
                if(maps[j].containsKey((int)cd))
                {
                    countAPj = maps[j].get((int)cd); //count of APs that are ending with nums[j] and comm-diff = cd
                }
                // If the ith map already contains APs ending with nums[i] and comm-diff = cd , we check it's count & increse it's count
                if(maps[i].containsKey((int)cd))
                {
                    countAPi = maps[i].get((int)cd); // count of APs that end with nums[i] and have common-diff = cd
                }

                maps[i].put((int)cd , (countAPj+countAPi+1));

                ans += countAPj ; 
            }
        }
        return ans;
    }
}

Solution(Javascript)

/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
  const max = nums.length

  if (max <= 2) {
    return 0
  }

  let ans = 0
  const dp = new Array(max).fill(0).map(() => new Map())
  for (let i = 1; i < max; i++) {
    const item = nums[i]
    for (let j = 0; j < i; j++) {
      const pre = nums[j]
      const diff = item - pre
      dp[i].set(diff, (dp[i].get(diff) || 0) + 1)
      if (dp[j].get(diff)) {
        dp[i].set(diff, dp[i].get(diff) + dp[j].get(diff))
        ans += dp[j].get(diff)
      }
    }  
  }
  return ans
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).