Сложность: hard
Дан целочисленный массив nums, вернуть количество всех арифметических подпоследовательностей nums.
Последовательность чисел называется арифметической, если она состоит как минимум из трех элементов и если разница между любыми двумя последовательными элементами одинаковая.
Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.
Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.
Пример:
Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
👨💻 Алгоритм:
1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.
2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.
3⃣Возвращаем количество всех арифметических подпоследовательностей.
😎 Решение:
class Solution {
constructor() {
this.n = 0;
this.ans = 0;
}
dfs(dep, A, cur) {
if (dep === this.n) {
if (cur.length < 3) return;
for (let i = 1; i < cur.length; i++) {
if (cur[i] - cur[i - 1] !== cur[1] - cur[0]) return;
}
this.ans++;
return;
}
this.dfs(dep + 1, A, cur);
cur.push(A[dep]);
this.dfs(dep + 1, A, cur);
cur.pop();
}
numberOfArithmeticSlices(A) {
this.n = A.length;
this.ans = 0;
this.dfs(0, A, []);
return this.ans;
}
}Ставь 👍 и забирай 📚 Базу знаний