8-line O(N^2) solution without long type conversion (with key points and comments)

  • 0

    C++ version of the popular DP solution in many posts here. My comment:

    • Use A[j] < 0 && A[i] > INT_MAX + A[j] instead of int to long casting for overflow checks;
    • Check of counts[j].count(d) is necessary; otherwise will get TLE for extremely large size of array.
    • Map value counts[i][d] is defined as the number of generic arithmetic sub array slice ending at index i with common difference d, where generic arithmetic sub array slice could have minimum length of 2.
    • The arithmetic sub array slice is defined by index subsequence instead of values, which means for subsequences with identical values but different indices are still considered different sub array slices (this is really critical in counting).
        int numberOfArithmeticSlices(vector<int>& A) {
          vector<unordered_map<int, int>> counts(A.size());
          int count, d, res = 0; auto i0 = A.begin();
          for (auto i = i0; i < A.end(); ++i)
            for (auto j = i0; j < i; ++j) {
              if (*j < 0 && *i > INT_MAX + *j || *j > 0 && *i < INT_MIN + *j) continue;
              res += (count = counts[j-i0].count(d = *i-*j)? counts[j-i0][d] : 0);
              counts[i-i0][d] += ++count;
          return res;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.