class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        Map<Integer, List<Integer>> indexMap = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            if (!indexMap.containsKey(A[i])) {
                indexMap.put(A[i], new ArrayList<>());
            }
            indexMap.get(A[i]).add(i);
        }
        int result = 0;
        for (List<Integer> indexes : indexMap.values()) {
            int size = indexes.size();
            if (size >= 3) {
                result += (1 << size) - 1 - size - size * (size - 1) / 2;
            }
        }
        for (int i = 0; i < A.length - 2; i++) {
            for (int j = i + 1; j < A.length; j++) {
                long diff = (long)A[j] - A[i];
                if (diff == 0 || diff < Integer.MIN_VALUE || diff > Integer.MAX_VALUE) {
                    continue;
                }
                result += dfs(A, j, diff, indexMap);
            }
        }
        return result;
    }

    private int dfs(int[] A, int index, long delta, Map<Integer, List<Integer>> indexMap) {
        long next = A[index] + delta;
        if (next < Integer.MIN_VALUE || next > Integer.MAX_VALUE || !indexMap.containsKey((int)next)) {
            return 0;
        }
        int result = 0;
        for (int i : indexMap.get((int)next)) {
            if (i <= index) continue;
            result += 1 + dfs(A, i, delta, indexMap);
        }
        return result;
    }
}

疑点1: 这个代码的主要思路是什么，可以概括一下嘛?

疑点2: 这个代码如果改成C++, 怎么避免整型溢出？

下面是我尝试改成的C++代码。

总共有101个test case，我改的这个代码 TLE，test case 过了67个。溢出的原因是什么？long long还不够吗?

class Solution {
    typedef long long LL;
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        if (A.size() <= 2)
            return 0;        
        unordered_map<LL, vector<LL>> indexDict;
        for (int i = 0; i < A.size(); i++) {
            if (!indexDict.count(A[i])) {
                indexDict[A[i]] = {};
            }
            indexDict[A[i]].push_back(i);
        }
        LL result = 0;
        for (auto kvp : indexDict) {
            int size = kvp.second.size();
            if (size >= 3) {
                result += (LL)(1 << size) - 1 - size - (LL)(size * (size - 1)) / 2;
            }
        }

        for (int i = 0; i < A.size() - 2; i++) {
            for (int j = i + 1; j < A.size(); j++) {
                LL diff = (LL)A[j] - A[i];
                if (diff == 0 || diff < INT_MIN || diff > INT_MAX) {
                    continue;
                }
                result += dfs(A, j, diff, indexDict);
            }
        }
        return int(result);      
    }

    LL dfs(vector<int>& A, long index, long delta, unordered_map<LL, vector<LL>> indexDict) {
        long next = A[index] + delta;
        if (next < INT_MIN || next > INT_MAX || !indexDict.count((int)next)) {
            return 0;
        }
        LL result = 0;
        for (int i : indexDict[(int)next]) {
            if (i <= index) continue;
            result += 1 + dfs(A, i, delta, indexDict);
        }
        return (int)result;
    }
};

疑点3: Java中的Integer.MIN_VALUE对应C++中的 INT_MIN还是 `std::numeric_limits<int>::min()` 或其他？

Java dfs2:

class Solution {
    int res = 0;
    Map<Integer, List<Integer>> idxs = new HashMap<>();

    public int numberOfArithmeticSlices(int[] A) {
        buildIdxMap(A);
        for (Map.Entry<Integer, List<Integer>> entry : idxs.entrySet()) {
            int d = entry.getValue().size();
            if ( d> 2)
                res += (1 << d) - 1 - d - d * (d - 1) / 2;
        }
        for (int j = 0; j < A.length-2; j++) {
            for (int i = j+1; i <A.length-1; i++) {
                long delta = (long)A[i] - (long)A[j];

                if (delta == 0)
                    continue;

                dfs(i,A[i]+delta,delta, 0);
            }
        }

        return res;
    }

    private void dfs(int i, long b, long delta, int c) {
        if(c>0)
            res++;

        if (b < Integer.MIN_VALUE || b > Integer.MAX_VALUE )
            return;

        List<Integer> l = idxs.get((int)b);
        if(l == null)
            return;

        int idx = Collections.binarySearch(l,i+1);  // Collections.binarySearch 改成 C++的low_bound理论上可以，但两者的返回值和找不到时的处理方式好像不同，Java如果没找到会在正确的地方插入, 返回-newIndex - 1
        if (idx < 0) idx = -idx - 1;

        for (int j = idx; j < l.size(); j++) {
            dfs(l.get(j),b+delta, delta, c+1);
        }
    }

    private void buildIdxMap(int[] A) {
        for (int i = 0; i < A.length; i++) {
            int a = A[i];
            List<Integer> l = idxs.get(a);
            if (l == null)
                idxs.put(a, l = new ArrayList<>());
            l.add(i);
        }
    }
}