leetcode 413. Arithmetic Slices

原题地址

https://leetcode.com/problems/arithmetic-slices/description/

题意

如果有这样的（P,Q），使得数组元素[P],[P+1],[P+2]....[Q-1],[Q]能构成一个元素数目至少为3的等差数列，则（P,Q）称为一个Arithmetic Slices。给定一个数组，找出其中所有Arithmetic Slices的数目。

思路

也算是LIS问题的变式吧。

代码

1

第一次，忘记了构成目标等差数列的元素在原数组里要是连续的，所以找出的数目比答案更多。（以及这里不知道为啥memset不work）

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        if(n==0) return 0;
        int max = A[0], min = A[0];
        int count = 0;
        for (int i = 1; i < n; i++) {
            if (max < A[i]) max = A[i];
            if (min > A[i]) min = A[i];
        }
        int diff1= max-min;
        int diff = 2*(max - min);
        int dp[diff + 1][n];
        // memset(dp, 1, sizeof(int) * (diff + 1) * n);
        for (int i = 0; i <= diff; i++) {
            for (int j = 0; j < n; j++)
                dp[i][j] = 1;
        }
        for (int i = 0; i <= diff; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < j; k++) {
                    if (A[j] - A[k] == i-diff1) {
                        dp[i][j] = dp[i][k] + 1;
                    }
                }
            }
        }
        for (int i = 0; i <= diff; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] >= 3)
                    count = count + dp[i][j] - 2;
            }
        }
        return count;
    }
};

用上面这代码的话，用

[1,2,3,4,5,6]

进行测试，输出的会是12，实际上只有10。这是因为把1,3，5,和2,4,6也算进去了

2

改正了这个问题(原先有3重循环，与目标元素之前的每一个元素比较，现在只与目标元素的恰好前一个元素比较) 之后

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        if (n == 0) return 0;
        int max = A[0], min = A[0];
        int count = 0;
        for (int i = 1; i < n; i++) {
            if (max < A[i]) max = A[i];
            if (min > A[i]) min = A[i];
        }
        int diff1 = max - min;
        int diff = 2 * (max - min);
        int dp[diff + 1][n];
        for (int i = 0; i <= diff; i++) {
            for (int j = 0; j < n; j++)
                dp[i][j] = 1;
        }
        for (int i = 0; i <= diff; i++) {
            for (int j = 1; j < n; j++) {
                if (A[j] - A[j - 1] == i - diff1) {
                    dp[i][j] = dp[i][j - 1] + 1;
                }
            }
        }
        for (int i = 0; i <= diff; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] >= 3)
                    count = count + dp[i][j] - 2;
            }
        }
        return count;
    }
};

再提交又直接得到了Runtime Error，似乎是因为开的dp 数组太大了（最大元素与最小元素的差的2倍*数组元素个数的二维数组）
于是去掉了最大元素与最小元素的差的2倍 这一维

3 最终答案

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        if (n == 0) return 0;
        int max = A[0], min = A[0];
        int count = 0;
        for (int i = 1; i < n; i++) {
            if (max < A[i]) max = A[i];
            if (min > A[i]) min = A[i];
        }
        int diff1 = max - min;
        int diff = 2 * (max - min);
        int dp[n];

        for (int i = 0; i <= diff; i++) {
            for (int j = 0; j < n; j++)
                dp[j] = 1;
            for (int j = 1; j < n; j++) {
                if (A[j] - A[j - 1] == i - diff1) {
                    dp[j] = dp[j - 1] + 1;
                }
            }

            for (int j = 0; j < n; j++) {
                if (dp[j] >= 3)
                    count = count + dp[j] - 2;
            }
        }
        return count;
    }
};