4sum
September 1, 2022
array-and-hashmapProblem URL: 4sum
We will sort the array and start from first element i, the take the next element j which is not equal to i, then take the next element as l, and the last element of the list as r, added them, compare them with the target, if we found a match, we add it to our result and move our l to next element which is not equal to current l. We repeat the whole process until i reaches last item - 3 position. Then we return our result.
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
nums.sort()
res = []
for i in range(n-3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
l, r = j+1, n-1
while l < r:
fourSum = nums[i] + nums[j] + nums[l] + nums[r]
if fourSum < target:
l += 1
elif fourSum > target:
r -= 1
else:
res.append([nums[i], nums[j], nums[l], nums[r]])
l += 1
while nums[l] == nums[l-1] and l < r:
l += 1
return res
Time Complexity: O(n^3)
Space Complexity: O(1)