arithmetic-slices-ii-subsequence（太难了）

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

太难了。。。

package com.company;

import java.util.*;

// 终于找到原因了。还是我重复加了

// 比如 46 46 47 48 49

// 用累积记录过往节点记录,发现超时了

// 参考了Discuss

// https://discuss.leetcode.com/topic/66725/o-n-2-mle-tle-in-c-try-this-one-concise-and-fast

// 其中 +1 这个地方 想了很久,终于想通了。意味着之前有一个长度为2的,会变成3.而为什么只加1就可以呢,因为用的是 last but one,

// 倒数第二个,帮忙记录最后一个可能的结果,而倒数第二个和前一个的连接,总是一对一的。。

// 实在太难了

class Solution {

    public int numberOfArithmeticSlices(int[] A) {

        // Need use Long to avoid gap exceeding

        Map<Integer, Map<Long, Integer>> mp = new HashMap<>();

        Set<Long> cSet = new HashSet<>();

        for (int k: A) {

            cSet.add((long)k);

        }

        int ret = 0;

        Map<Long, Integer> lastMp;

        long gap;

        int tmp;

        int curRet;

        for (int i=0; i<A.length; i++) {

            Map<Long, Integer> tmpMp = new HashMap<>();

            for (int j=i-1; j>=0; j--) {

                gap = (long)A[i] - (long)A[j];

                if (tmpMp.containsKey(gap)) {

                    curRet = tmpMp.get(gap);

                }

                else {

                    curRet = 0;

                }

                lastMp = mp.get(j);

                if (!lastMp.containsKey(gap)) {

                    tmp = 0;

                }

                else {

                    tmp = lastMp.get(gap);

                    ret += tmp;

                }

                //System.out.printf("val %d gap %d\n", A[i], gap);

                if (cSet.contains(A[i] + gap)) {

                    tmpMp.put(gap, curRet + tmp + 1);

                    //System.out.printf("here val %d gap %d\n", A[i], gap);

                }

            }

            mp.put(i, tmpMp);

        }

        return ret;

    }

}

public class Main {

    public static void main(String[] args) throws InterruptedException {

        System.out.println("Hello!");

        Solution solution = new Solution();

        // Your Codec object will be instantiated and called as such:

        int[] A = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

        int ret = solution.numberOfArithmeticSlices(A);

        System.out.printf("ret:%d\n", ret);

        System.out.println();

    }

}