leetcode

commit 7812da12324a5306dc5f6d52fdfceab7762d5dd5
parent e549c87028ba7f9fdaa34b547851b79e97a0e8c7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed,  8 Feb 2023 19:29:14 +0100

Data Structure II: Day 5

Diffstat:
A
Problems/0334.cpp
 | 
15
+++++++++++++++
A
Problems/0560.cpp
 | 
17
+++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 34 insertions(+), 0 deletions(-)
diff --git a/Problems/0334.cpp b/Problems/0334.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+  bool increasingTriplet(vector<int> &nums) {
+    int a = INT_MAX, b = INT_MAX;
+    for (int x : nums) {
+      if (x <= a)
+        a = x;
+      else if (x <= b)
+        b = x;
+      else
+        return true;
+    }
+    return false;
+  }
+};
diff --git a/Problems/0560.cpp b/Problems/0560.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+  int subarraySum(vector<int> &nums, int k) {
+    int n = nums.size(), res = 0, sum = 0;
+    unordered_map<int, int> um;
+    vector<int> prefix(n);
+    for (int i = 0; i < n; i++) sum = prefix[i] = sum + nums[i];
+
+    for (int i = 0; i < n; i++) {
+      if (prefix[i] == k) res++;
+      if (um.count(prefix[i] - k)) res += um[prefix[i] - k];
+      um[prefix[i]]++;
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -176,6 +176,7 @@ for solving problems.
 |  0310  |   Medium   | [Minimum Height Trees](Problems/0310.cpp)                                                        |
 |  0326  |    Easy    | [Power of Three](Problems/0326.cpp)                                                              |
 |  0328  |   Medium   | [Odd Even Linked List](Problems/0328.cpp)                                                        |
+|  0334  |   Medium   | [Increasing Triplet Subsequence](Problems/0334.cpp)                                              |
 |  0338  |    Easy    | [Counting Bits](Problems/0338.cpp)                                                               |
 |  0342  |    Easy    | [Power of Four](Problems/0342.cpp)                                                               |
 |  0344  |    Easy    | [Reverse String](Problems/0344.cpp)                                                              |
@@ -227,6 +228,7 @@ for solving problems.
 |  0556  |   Medium   | [Next Greater Element III](Problems/0556.cpp)                                                    |
 |  0557  |    Easy    | [Reverse Words in a String III](Problems/0557.cpp)                                               |
 |  0559  |    Easy    | [Maximum Depth of N-ary Tree](Problems/0559.cpp)                                                 |
+|  0560  |   Medium   | [Subarray Sum Equals K](Problems/0560.cpp)                                                       |
 |  0561  |    Easy    | [Array Partition](Problems/0561.cpp)                                                             |
 |  0563  |    Easy    | [Binary Tree Tilt](Problems/0563.cpp)                                                            |
 |  0566  |    Easy    | [Reshape the Matrix](Problems/0566.cpp)                                                          |