leetcode

commit 1f75a5874ad6db72c5715312e9b61f403fb34767
parent 74ba4dea073e7d5284195d863285e4ffe73cbdc8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 21 Sep 2024 19:20:42 +0200

1 Random Problem

Diffstat:
A
Problems/0611.cpp
 | 
20
++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 21 insertions(+), 0 deletions(-)
diff --git a/Problems/0611.cpp b/Problems/0611.cpp
@@ -0,0 +1,20 @@
+class Solution {
+  public:
+    int triangleNumber(vector<int> &nums) const {
+        const int n = size(nums);
+        int res = 0;
+
+        sort(begin(nums), end(nums));
+        for (int k = 2; k < n; k++) {
+            int i = 0, j = k - 1;
+            while (i < j) {
+                if (nums[i] + nums[j] <= nums[k])
+                    i++;
+                else
+                    res += j - i, j--;
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -426,6 +426,7 @@ for solving problems.
 |  0608  |   Medium   | [Tree Node](Problems/0608.cpp)                                                                     |
 |  0609  |   Medium   | [Find Duplicate File in System](Problems/0609.cpp)                                                 |
 |  0610  |    Easy    | [Triangle Judgement](Problems/0610.cpp)                                                            |
+|  0611  |   Medium   | [Valid Triangle Number](Problems/0611.cpp)                                                         |
 |  0617  |    Easy    | [Merge Two Binary Trees](Problems/0617.cpp)                                                        |
 |  0619  |    Easy    | [Biggest Single Number](Problems/0619.cpp)                                                         |
 |  0620  |    Easy    | [Not Boring Movies](Problems/0620.cpp)                                                             |