added problems

AlveeM · AlveeM · commit 0e29bf176c57 · 2020-12-13T20:33:30.000-05:00
diff --git a/leetcode/patterns/02-two-pointers/09_4sum.py b/leetcode/patterns/02-two-pointers/09_4sum.py
@@ -0,0 +1,37 @@
+class Solution:
+    def fourSum(self, nums, target):
+        self.res = []
+        if len(nums) < 4: return self.res
+        
+        nums.sort()
+        if nums[0] * 4 > target or nums[-1] * 4 < target: return self.res
+        
+        for i in range(len(nums)-3):
+            if i > 0 and nums[i] == nums[i-1]:
+                continue
+            for j in range(i+1, len(nums)-2):
+                if j > i + 1 and nums[j] == nums[j-1]:
+                    continue
+                self.findPair(nums, target, i, j)
+                
+        return self.res
+    
+    def findPair(self, nums, target, a_idx, b_idx):
+        l = b_idx + 1
+        r = len(nums) - 1
+        
+        while l < r:
+            a, b, c, d = nums[a_idx], nums[b_idx], nums[l], nums[r]
+            total = a + b + c + d
+            if total == target:
+                self.res.append([a, b, c, d])
+                l += 1
+                r -= 1
+                while l < r and nums[l] == nums[l-1]:
+                    l += 1
+                while l < r and nums[r] == nums[r+1]:
+                    r -= 1
+            elif total < target:
+                l += 1
+            else:
+                r -= 1
diff --git a/leetcode/patterns/02-two-pointers/10_backspace_string_compare.py b/leetcode/patterns/02-two-pointers/10_backspace_string_compare.py
@@ -0,0 +1,33 @@
+class Solution:
+    def backspaceCompare(self, S: str, T: str) -> bool:
+        i1 = len(S) - 1
+        i2 = len(T) - 1
+        
+        while i1 >= 0 or i2 >= 0:
+            i1 = self.nextIndex(S, i1)
+            i2 = self.nextIndex(T, i2)
+            if i1 < 0 and i2 < 0:
+                return True
+            if i1 < 0 or i2 < 0:
+                return False
+            if S[i1] != T[i2]:
+                return False
+            i1 -= 1
+            i2 -= 1
+        
+        return True
+        
+    def nextIndex(self, string, idx):
+        backspace_count = 0
+        
+        while idx >= 0:
+            if string[idx] == '#':
+                backspace_count += 1
+            elif backspace_count > 0:
+                backspace_count -= 1
+            else:
+                break
+            idx -= 1
+        
+        return idx
+
diff --git a/leetcode/patterns/02-two-pointers/11_shortest_unsorted_continuous_subarray.py b/leetcode/patterns/02-two-pointers/11_shortest_unsorted_continuous_subarray.py
@@ -0,0 +1,27 @@
+class Solution:
+    def findUnsortedSubarray(self, nums):
+        n = len(nums)
+        l = 0
+        r = n - 1
+        
+        while l < n - 1 and nums[l] <= nums[l+1]:
+            l += 1
+            
+        if l == n-1: return 0
+
+        while r > 0 and nums[r] >= nums[r-1]:
+            r -= 1
+        
+        sub_max = float('-inf')
+        sub_min = float('inf')
+        for i in range(l, r+1):
+            sub_max = max(sub_max, nums[i])
+            sub_min = min(sub_min, nums[i])
+
+        while l > 0 and nums[l-1] > sub_min:
+            l -= 1
+            
+        while r < n-1 and nums[r+1] < sub_max:
+            r += 1
+            
+        return r - l + 1
