3sum
1# @leet start 2class Solution: 3 def threeSum(self, nums: list[int]) -> list[list[int]]: 4 """ 5 Three sum involves finding all triplets in a list that sum to 0. 6 To do this, we can iterate through the array, fixing one number as our 7 third number, and then solving 2 sum on the remaining items. 8 9 To make this easy with two pointers, we first sort the nums, and then 10 iterate through the numbers. Since our numbers are sorted, and we dont 11 want to accept duplicates, we can skip duplicates with the condition 12 i > 0 and a == nums[i - 1]. 13 We then check all the numbers to the right of the current number, and 14 check if we have a matching triplet. If we do, we add it to the list. 15 If our sum is too large, we decrement the right pointer to decrease the 16 sum, and if the sum is too small, increment the left pointer to increase 17 the sum. 18 19 Finally, while we loop through the array, since duplicates can persist, 20 we want to keep incrementing the left pointer as long as its the same number. 21 """ 22 nums.sort() 23 res = [] 24 25 for i, a in enumerate(nums): 26 if i > 0 and a == nums[i - 1]: 27 continue 28 l, r = i + 1, len(nums) - 1 29 30 while l < r: 31 three_sum = a + nums[l] + nums[r] 32 if three_sum < 0: 33 l += 1 34 elif three_sum > 0: 35 r -= 1 36 else: 37 res.append([a, nums[l], nums[r]]) 38 l += 1 39 while nums[l] == nums[l - 1] and l < r: 40 l += 1 41 return res 42 43 44# @leet end 45 46 47def test(): 48 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def threeSum(self, nums: list[int]) -> list[list[int]]: 5 """ 6 Three sum involves finding all triplets in a list that sum to 0. 7 To do this, we can iterate through the array, fixing one number as our 8 third number, and then solving 2 sum on the remaining items. 9 10 To make this easy with two pointers, we first sort the nums, and then 11 iterate through the numbers. Since our numbers are sorted, and we dont 12 want to accept duplicates, we can skip duplicates with the condition 13 i > 0 and a == nums[i - 1]. 14 We then check all the numbers to the right of the current number, and 15 check if we have a matching triplet. If we do, we add it to the list. 16 If our sum is too large, we decrement the right pointer to decrease the 17 sum, and if the sum is too small, increment the left pointer to increase 18 the sum. 19 20 Finally, while we loop through the array, since duplicates can persist, 21 we want to keep incrementing the left pointer as long as its the same number. 22 """ 23 nums.sort() 24 res = [] 25 26 for i, a in enumerate(nums): 27 if i > 0 and a == nums[i - 1]: 28 continue 29 l, r = i + 1, len(nums) - 1 30 31 while l < r: 32 three_sum = a + nums[l] + nums[r] 33 if three_sum < 0: 34 l += 1 35 elif three_sum > 0: 36 r -= 1 37 else: 38 res.append([a, nums[l], nums[r]]) 39 l += 1 40 while nums[l] == nums[l - 1] and l < r: 41 l += 1 42 return res
def
threeSum(self, nums: list[int]) -> list[list[int]]:
4 def threeSum(self, nums: list[int]) -> list[list[int]]: 5 """ 6 Three sum involves finding all triplets in a list that sum to 0. 7 To do this, we can iterate through the array, fixing one number as our 8 third number, and then solving 2 sum on the remaining items. 9 10 To make this easy with two pointers, we first sort the nums, and then 11 iterate through the numbers. Since our numbers are sorted, and we dont 12 want to accept duplicates, we can skip duplicates with the condition 13 i > 0 and a == nums[i - 1]. 14 We then check all the numbers to the right of the current number, and 15 check if we have a matching triplet. If we do, we add it to the list. 16 If our sum is too large, we decrement the right pointer to decrease the 17 sum, and if the sum is too small, increment the left pointer to increase 18 the sum. 19 20 Finally, while we loop through the array, since duplicates can persist, 21 we want to keep incrementing the left pointer as long as its the same number. 22 """ 23 nums.sort() 24 res = [] 25 26 for i, a in enumerate(nums): 27 if i > 0 and a == nums[i - 1]: 28 continue 29 l, r = i + 1, len(nums) - 1 30 31 while l < r: 32 three_sum = a + nums[l] + nums[r] 33 if three_sum < 0: 34 l += 1 35 elif three_sum > 0: 36 r -= 1 37 else: 38 res.append([a, nums[l], nums[r]]) 39 l += 1 40 while nums[l] == nums[l - 1] and l < r: 41 l += 1 42 return res
Three sum involves finding all triplets in a list that sum to 0. To do this, we can iterate through the array, fixing one number as our third number, and then solving 2 sum on the remaining items.
To make this easy with two pointers, we first sort the nums, and then iterate through the numbers. Since our numbers are sorted, and we dont want to accept duplicates, we can skip duplicates with the condition i > 0 and a == nums[i - 1]. We then check all the numbers to the right of the current number, and check if we have a matching triplet. If we do, we add it to the list. If our sum is too large, we decrement the right pointer to decrease the sum, and if the sum is too small, increment the left pointer to increase the sum.
Finally, while we loop through the array, since duplicates can persist, we want to keep incrementing the left pointer as long as its the same number.
def
test():