446. Arithmetic Slices II - Subsequence 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) {
            return 0;
        }

        int n = nums.length;

        // 定义 dp[i][j] 为以 nums[i] 结尾的公差值为 j 的弱等差数列的个数
        List<Map<Long, Integer>> dp = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            dp.add(new HashMap<>());
        }

        int count = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long diff = (long)nums[i] - nums[j]; // 注意此处需要计算前显式转型
                dp.get(i).put(diff, dp.get(i).getOrDefault(diff, 0) + dp.get(j).getOrDefault(diff, 0) + 1);

                // dp.get(j) 的 Map 中含有 diff 说明才能组成长度大于等于 3 的等差数列
                count += dp.get(j).getOrDefault(diff, 0);
            }
        }

        return count;
    }
}

References

446. Arithmetic Slices II - Subsequence