leetcode

commit 546dc79fdfe45a4a83af84ef08f25fb857fc0f99
parent 1c5c912fcef26b4a5a3b14534dcc94149bd47a20
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat,  8 Apr 2023 12:32:40 +0200

Random Problem

Diffstat:
A
Problems/0018.cpp
 | 
30
++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 31 insertions(+), 0 deletions(-)
diff --git a/Problems/0018.cpp b/Problems/0018.cpp
@@ -0,0 +1,30 @@
+class Solution {
+public:
+  vector<vector<int>> fourSum(vector<int> &nums, int target) {
+    vector<vector<int>> res;
+    int n = nums.size();
+
+    sort(nums.begin(), nums.end());
+    for (int i = 0; i < n; i++) {
+      for (int j = i + 1; j < n; j++) {
+        long long goal = (long long)target - nums[i] - nums[j];
+        int k = j + 1, l = n - 1;
+        while (k < l) {
+          long long crnt = nums[k] + nums[l];
+          if (crnt > goal)
+            l--;
+          else if (crnt < goal)
+            k++;
+          else {
+            res.push_back({nums[i], nums[j], nums[k], nums[l]});
+            k++, l--;
+            while (k < l && nums[l] == nums[l + 1]) l--;
+          }
+        }
+        while (j + 1 < n && nums[j] == nums[j + 1]) ++j;
+      }
+      while (i + 1 < n && nums[i] == nums[i + 1]) ++i;
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -40,6 +40,7 @@ for solving problems.
 |  0015  |   Medium   | [3Sum](Problems/0015.cpp)                                                                        |
 |  0016  |   Medium   | [3Sum Closest](Problems/0016.cpp)                                                                |
 |  0017  |   Medium   | [Letter Combinations of a Phone Number](Problems/0017.cpp)                                       |
+|  0018  |   Medium   | [4Sum](Problems/0018.cpp)                                                                        |
 |  0019  |   Medium   | [Remove Nth Node From the End of List](Problems/0019.cpp)                                        |
 |  0020  |    Easy    | [Valid Parentheses](Problems/0020.cpp)                                                           |
 |  0021  |    Easy    | [Merge Two Sorted Lists](Problems/0021.cpp)                                                      |