commit 6de108a5eb9bb82f24b8c410b5d0368482b94caf parent 780df78caa1e1603146ce55fa2b9be345c397374 Author: Dimitrije Dobrota <mail@dimitrijedobrota.com> Date: Sun, 7 Jan 2024 16:26:53 +0000 Daily Problem Diffstat:
| A | Problems/0446.cpp | | | 16 | ++++++++++++++++ |
| M | README.md | | | 1 | + |
2 files changed, 17 insertions(+), 0 deletions(-)
diff --git a/Problems/0446.cpp b/Problems/0446.cpp @@ -0,0 +1,16 @@ +class Solution { + public: + int numberOfArithmeticSlices(const vector<int> &nums) const { + vector<unordered_map<long long, int>> dp(size(nums)); + int res = 0; + for (int i = 1; i < size(nums); i++) { + for (int j = 0; j < i; j++) { + const long long diff = (long long)nums[i] - nums[j]; + const int cnt = dp[j].count(diff) ? dp[j][diff] : 0; + dp[i][diff] += cnt + 1; + res += cnt; + } + } + return res; + } +}; diff --git a/README.md b/README.md @@ -324,6 +324,7 @@ for solving problems. | 0442 | Medium | [Find All Duplicates in an Array](Problems/0442.cpp) | | 0443 | Medium | [String Compression](Problems/0443.cpp) | | 0445 | Medium | [Add Two Numbers II](Problems/0445.cpp) | +| 0446 | Hard | [Arithmetic Slices II - Subsequence](Problems/0446.cpp) | | 0448 | Easy | [Find All Numbers Disappeared in an Array](Problems/0448.cpp) | | 0450 | Medium | [Delete Node in a BST](Problems/0450.cpp) | | 0451 | Medium | [Sort Characters By Frequency](Problems/0451.cpp) |