commit 71190176774e5c600d9869afc2c7ef13099946c5
parent eca5bf6fddad624cc8909c8ff9b0cfae8910f046
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Fri, 17 Feb 2023 15:42:43 +0100
LeetCode 75 II: Day 14
Diffstat:
3 files changed, 45 insertions(+), 0 deletions(-)
diff --git a/Problems/0016.cpp b/Problems/0016.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+ int threeSumClosest(vector<int> &nums, int target) {
+ int n = nums.size(), delta = INT_MAX / 2, res = 0;
+ sort(nums.begin(), nums.end());
+ for (int i = 0; i < n; i++) {
+ int j = i + 1;
+ int k = n - 1;
+ while (j < k) {
+ int sum = nums[i] + nums[j] + nums[k];
+ if (abs(target - sum) < delta) {
+ delta = abs(target - sum);
+ res = sum;
+ }
+ (sum > target) ? k-- : j++;
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/0076.cpp b/Problems/0076.cpp
@@ -0,0 +1,23 @@
+class Solution {
+public:
+ string minWindow(string s, string t) {
+ vector<int> remaining(128, 0);
+ for (char c : t) remaining[c]++;
+
+ int required = t.size();
+ int min = INT_MAX, start = 0, left = 0, i = 0;
+ while (i <= s.size() && start < s.size()) {
+ if (required) {
+ if (i == s.size()) break;
+ if (--remaining[s[i++]] >= 0) required--;
+ } else {
+ if (i - start < min) {
+ min = i - start;
+ left = start;
+ }
+ if (++remaining[s[start++]] > 0) required++;
+ }
+ }
+ return min == INT_MAX ? "" : s.substr(left, min);
+ }
+};
diff --git a/README.md b/README.md
@@ -36,6 +36,7 @@ for solving problems.
| 0013 | Easy | [Roman to Integer](Problems/0013.cpp) |
| 0014 | Easy | [Longest Common Prefix](Problems/0014.cpp) |
| 0015 | Medium | [3Sum](Problems/0015.cpp) |
+| 0016 | Medium | [3Sum Closest](Problems/0016.cpp) |
| 0017 | Medium | [Letter Combinations of a Phone Number](Problems/0017.cpp) |
| 0019 | Medium | [Remove Nth Node From the End of List](Problems/0019.cpp) |
| 0020 | Easy | [Valid Parentheses](Problems/0020.cpp) |
@@ -76,6 +77,7 @@ for solving problems.
| 0072 | Hard | [Edit Distance](Problems/0072.cpp) |
| 0074 | Medium | [Search a 2D Matrix](Problems/0074.cpp) |
| 0075 | Medium | [Sort Colors](Problems/0075.cpp) |
+| 0076 | Hard | [Minimum Window Substring](Problems/0076.cpp) |
| 0077 | Medium | [Combinations](Problems/0077.cpp) |
| 0078 | Medium | [Subsets](Problems/0078.cpp) |
| 0079 | Medium | [Word Search](Problems/0079.cpp) |
