Leetcode 446 Solution

This article provides solution to leetcode question 446 (arithmetic-slices-ii-subsequence)
Categories:
Tags:
Access this page by simply typing in "lcs 446" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/arithmetic-slices-ii-subsequence

Solution

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        if (n == 0)
            return 0;

        unordered_map<int, int> a[n];
        int res = 0;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                int64_t diff = (int64_t)A[i] - (int64_t)A[j];

                if (diff >= INT_MAX || diff <= INT_MIN)
                    continue;

                if (a[j].find(diff) == a[j].end())
                    a[i][diff]++;
                else
                {
                    a[i][diff] += a[j][diff] + 1;
                    res += a[j][diff];
                }
            }
        }

        return res;
    }
};