Сложность: 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 {
private $n;
private $ans;
private function dfs($dep, $A, $cur) {
if ($dep == $this->n) {
if (count($cur) < 3) return;
for ($i = 1; $i < count($cur); $i++) {
if ($cur[$i] - $cur[$i - 1] != $cur[1] - $cur[0]) return;
}
$this->ans++;
return;
}
$this->dfs($dep + 1, $A, $cur);
array_push($cur, $A[$dep]);
$this->dfs($dep + 1, $A, $cur);
}
public function numberOfArithmeticSlices($A) {
$this->n = count($A);
$this->ans = 0;
$this->dfs(0, $A, []);
return $this->ans;
}
}Ставь 👍 и забирай 📚 Базу знаний