題目鏈接

1. 思路講解

我們要知道以某個位置為結(jié)尾的子序列的數(shù)量，可以通過它的以上一位置的為結(jié)尾的子序列的數(shù)量得知，也就是說，這是一個dp問題。

1.1 dp表的創(chuàng)建

dp問題我們需要創(chuàng)建dp表，如果我們單純使用dp[i]來表示以 i 位置為結(jié)尾的子序列的數(shù)量是完全不夠的。因為我們不知道以 i-1 位置為結(jié)尾的等差數(shù)列是怎樣的，它的公差是幾我們是不知道的。也就是說，我們不確定 i 位置的元素是否能跟到以 i - 1 位置為結(jié)尾的數(shù)列的后面。

但是，如果知道了數(shù)列的后兩個元素，也就是知道了 i - 1 位置以及數(shù)列中上一個位置的元素，就能知道數(shù)列的公差了，也就能知道 i 位置的元素是否能跟到后面了，所以我們需要用兩個元素來表示每個dp位置。

創(chuàng)建二維dp表，dp[i][j]表示以 i 位置的元素為數(shù)列倒數(shù)第二個元素，以 j 位置的元素為數(shù)列倒數(shù)第一個元素，為結(jié)尾的數(shù)列數(shù)量有多少。（我們?nèi)藶橐?guī)定i < j）

1.2 狀態(tài)轉(zhuǎn)移方程

nums[j] - nums[i]可以得到公差，再由 num[i] - 公差 可以得到上一項的值，記為 a，我們需要知道這個 a 值在nums中是否存在且是否在 i 位置的前面，兩個條件都滿足才符合題意。

記 a 在nums中的下標為k（至于怎么找到這個k下面會說），我們要找到以 i 和 j 位置為結(jié)尾的等差數(shù)列的個數(shù)，其實找到所有 k 和 i 位置元素結(jié)尾的等差數(shù)列的個數(shù)相加即可（a元素在nums中的位置不只一個，那么k可能就不只一個）。并且也需額外加上一個數(shù)列，就是 k，i ，j，本身所構(gòu)成的等差數(shù)列。

那么狀態(tài)轉(zhuǎn)移方程就為：dp[i][j] += dp[k][i] + 1

1.3 使用哈希表找到k

我們寫代碼的時候，遍歷所有 i 和 j 的組合，時間復(fù)雜度就已經(jīng)到達 N^2 了，如果此時再在數(shù)組中去尋找 k ，那么時間復(fù)雜度就 N^3了，這大概率是會超時的。

我們可以在dp之前，使用哈希表去將<所有元素，數(shù)組下標>綁定在一起，放在哈希表中，這樣我們得到了 a 之后，就可以使用哈希表很快地查找到 k 了。

1.4 初始化

剛開始，以 i，j 位置為結(jié)尾，只有兩個元素，不符合題目中的等差數(shù)列，可以記為 0 ，所以我們初始化的時候?qū)p表中所有的值初始化為 0 即可。又因為，vector會默認初始化為0，所以我們不用手動初始化了。

1.5 返回值

我們要求的是所有的等差數(shù)列，所以我們要將所有符合題意的dp[i][j]都加起來然后返回。

1.6 該題坑爹的一點

雖然題目已經(jīng)說了，返回值以及各個元素的值都在int范圍內(nèi)，但是我們求a的時候，a的值可能會超出int的范圍從而出錯，所以我們將a的類型要設(shè)置為long long。然后用a查找k用的是hash，所以hash的第一個類型也要為long long。

2. 代碼編寫

文章來源地址http://www.zghlxwxcb.cn/news/detail-622428.html

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        // 創(chuàng)建哈希表，便于很快地找到k
        // 因為k不只一個，所以用vector來存儲
        unordered_map<long long, vector<int>> hash;
        for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);

        // 創(chuàng)建二維dp表，第一維為數(shù)列的倒數(shù)第二個元素，第二維為數(shù)列的倒數(shù)第一個元素
        vector<vector<int>> dp(n, vector<int>(n));
        
        int ret = 0; // 所有數(shù)組的數(shù)量

        // i為nums第0個位置時，不管j為幾，dp[0][j]都為0，因為只有兩個元素
        // 所以從第1個位置開始填表即可，且i一定不為nums最后一個元素
        for (int i = 1; i < n - 1; ++i)
        {
            // j從i+1開始，一直到最后一個位置，尋找符合題意的情況
            for (int j = i + 1; j < n; ++j)
            {
                long long a = (long long)2*nums[i] - nums[j];
                if (hash.count(a)) // 看a是否存在于hash中
                {
                    // 如果存在，遍歷a對應(yīng)的vector
                    for (auto k : hash[a])
                    {
                        // k需要小于i
                        if (k < i) dp[i][j] += dp[k][i] + 1;
                    }
                } 
                ret += dp[i][j];
            }
        }
        return ret;
    }
};

到了這里，關(guān)于【LeetCode】446. 等差數(shù)列劃分II -- 子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！