[Python][LeetCode] 15. 3Sum

Link

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # point 1. For making the basis of moving two pointers
        answer = []  # Initializing 'answer' by making empty list
        
        # point 2. The main thinking is fixing position of 'i' then moving 'l' and 'r'
        for i in range(len(nums) - 2):  
          
        # point 3. If the first number of list is 'natural number', it doesn't need for checking.
        # Because we already have 'sorted nums'. But our goal is making '0' by summing 3 elements.
            if nums[i] > 0:
                break  
              
              
              # point 4. It needs 'example' for proving.
              # In that condition of 'nums[i] == nums[i-1]', it will make just same combination.
              # So preventing 'time' issue, It could be better to use this code.
            if i > 0 and nums[i] == nums[i-1]:
                continue  
            
            # Those two lines are just 'default' of 'l' and 'r' in 'two pointer' problem
            l = i + 1  
            r = len(nums) - 1 
            
            while l < r:  
                total = nums[i] + nums[l] + nums[r]

                # This condition is just for checking all the elements.
                # So I guess that the contents of condition is not important
                if total < 0: 
                    l += 1 
                elif total > 0:
                    r -= 1  
                else:
                    triplet = [nums[i], nums[l], nums[r]]  
                    answer.append(triplet)  
                    
                    
                    # point 5. Those two while loop exist for 'keeping looping'
                    # These means that as soon as you append the 'triplet',
                    # we have to moving the index of 'l' or 'j'.
                    while l < r and nums[l] == triplet[1]:
                        l += 1  
                    while l < r and nums[r] == triplet[2]:
                        r -= 1  
        return answer  

Summary

1. For making the basis of moving two pointers

nums.sort() 

2.The main thinking is fixing position of ‘i’ then moving ‘l’ and ‘r’ 3.If the first number of list is ‘natural number’, it doesn’t need for checking. because we already have ‘sorted nums’. But our goal is making ‘0’ by summing 3 elements.

if nums[i] > 0:
    break  

4.

if i > 0 and nums[i] == nums[i-1]:
    continue  

This part is necessary to prevent duplicate results. Since the nums array is already sorted, if the same number appears consecutively, it is likely that combinations starting with that number have already been considered. Thus, re-evaluating combinations starting with the same number could lead to duplicate results.

For example, consider the nums array [-1, -1, 0, 1, 2]. At i=0, -1 is used as the starting point, and appropriate l and r are found to discover the combination [-1, 0, 1]. Then at i=1, -1 is again the starting point, which would re-evaluate combinations already considered at i=0. To avoid this redundancy, the condition if i > 0 and nums[i] == nums[i-1]: continue is used to skip over duplicate combinations involving the same starting number. This enhances the efficiency of the algorithm and removes duplicate results. (Thank you GPT…!)

5.

while l < r and nums[l] == triplet[1]:
    l += 1  
while l < r and nums[r] == triplet[2]:
    r -= 1  

Those two while loop exist for ‘keeping looping’. These means that as soon as you append the ‘triplet’, we have to moving the index of ‘l’ or ‘j’.