leetcode 446. Arithmetic Slices II - Subsequence | 446. 等差数列划分 II - 子序列（动态规划）

蔚落 2022-09-11 03:15 116阅读 0赞

## 题目 ##

[https://leetcode.com/problems/arithmetic-slices-ii-subsequence/][https_leetcode.com_problems_arithmetic-slices-ii-subsequence]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

找等差子数列，详见注释。

一个月前做过，没通过，今天 daily challenge 又看了下，只是 int 的越界问题，转成 long 就好了。

class Solution { 
        public int numberOfArithmeticSlices(int[] A) { 
            int n = A.length;
            long ans = 0;
            Map<Long, Long>[] cnt = new Map[n]; // [i]<dif,cnt>表示以i为结尾，公差为dif的数列个数
            for (int i = 0; i < n; i++) {  // a[n]
                cnt[i] = new HashMap<>(i);
                for (int j = 0; j < i; j++) {  // a[n-1]
                    long dif = (long) A[i] - A[j];
                    long sum = cnt[j].getOrDefault(dif, (long) 0); // 以a[n]结尾，dif为公差的情况下，找以a[n-1]结尾的等差数列个数
                    long origin = cnt[i].getOrDefault(dif, (long) 0); // 拿到map中原来的数，避免put覆盖。主要针对a[n]==a[n-1]的情况，即公差为0的常数列。
                    cnt[i].put(dif, origin + sum + 1);
                    ans += sum; // 只有找到以a[n-1]结尾的等差数列个数才有资格加入到sum中，因为等差数列至少要3个元素
                }
            }
            return (int) ans;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_arithmetic-slices-ii-subsequence]: https://leetcode.com/problems/arithmetic-slices-ii-subsequence/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/7edf1b1305454c13a1800ab97e13f7f9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/c934ce4bc297487195184e4dcce8e6dc.png