Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Python Algorithm Q9

Q9 3Sum

Q

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Sample Input

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: nums = []
Output: []

Input: nums = [0]
Output: []

Constraints

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

1. My Solution <- Given Solution #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort() #idx is useless so sort it in order to use two-pointer + a

        for i in range(len(nums)-2): #'cause next two elements i, i+1, i+2
            if i>0 and nums[i]==nums[i-1]: #when current value is same as the previous one, skip it!
                continue
            
            left, right = i+1, len(nums) - 1 #loop with i then beyond i idx, two-pointer sol begins.
            
            while left < right:
                sums = nums[i] + nums[left] + nums[right]
                if sums > 0:
                    right -= 1
                elif sums < 0:
                    left += 1
                else:
                    ans.append([nums[i], nums[left], nums[right]])
                    
                    '''
                    the most important part in this sol.
                    #after you sort the input list, there will be duplicated values.
                    Skipping these valeus will be the main point to decrease the time.
                    Therefore, continuously repeat moving pointer.
                    '''
                    while left < right and nums[left] == nums[left+1]:
                        left += 1 #even if left +=1 but same situation, repeat it
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1 #vice versa               
                    
                    right -= 1 #why moved both? It is because sum should be 0 anyway. only moving one pointer is meaningless. 
                    left += 1
        return ans

ans = Solution()
nums = [-1,0,1,2,-1,-4]
#nums = [0]
pt = ans.threeSum(nums)
print(pt)

[Using two-pointer]
Main concept is not that difficult. Loop with the for loop starting from N-th element. Then use two-pointer in the array after the N-th element(=[N:]). What is the most important in this solution is skipping overlapped case. After sorting the array, you can easily find countless overlapped values. By skipping, execution time improves and prevents duplicated values flowing into the answer array. In the code above, there are three skip points.

First one is in the for loop. When in the for loop, you don’t need to repeat the process(two-pointer) for the same case. So naturelly skip it with “if i>0 and nums[i]==nums[i-1]: continue”

(**i>0인 이유는 이전 인덱스랑 비교하기 때문에 i-1이랑 비교하기 때문이다.)

Second and third one is right & left idx in two-pointer. When the values that the pointer indicates meet the condition, not just right– & left++. To prevent overlapped values exist in answer array, continuously skip it like “while left < right and nums[left] == nums[left+1]: left += 1”. Same as right case.

(** 중복되는 idx를 모두 건너띄고도 아래 한번 더 넘기는데 맞나라는 질문이 들 수 있다. 조건문을 잘 보면 현재와 다음을 비교하고 있다. 현재 기준으로 다음 거랑 같을 때까지만 반복하고, 탈출하는 순간은 다음 것과 더 이상 같지 않을 때, 즉 while 탈출 직전 i가 마지막으로 가르키는 idx는 아직 중복된 값을 가르키고 있다. 맨 마지막 right–, left++를 거쳐야 비로소 idx가 중복되지 않은 값을 가르키도록 바뀌는 것이다.)

Overall Review

Algo itself is quite affordable. Applying two-pointer with loop is much familiar then before. However, still some difficulties, mostly execution timeout, exists. When handling these kind of problems, you should be aware of time-out on account of countless overlapped cases. Don’t forget to skip those properly…

참고