[파이썬][Leetcode][릿코드] 3Sum
1. 문제Permalink
15. 3Sum
Medium
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.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = [] Output: []
Example 3:
Input: nums = [0] Output: []
Constraints:
0 <= nums.length <= 3000-105 <= nums[i] <= 105
출처: Leetcode, https://leetcode.com/
2. 해결방법 시간복잡도Permalink
- 이분탐색 O(N^2)
3. 문제 해결 및 코드Permalink
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def threeSum(self, nums: List[int]) -> List[List[int]]: | |
| # 이중 반복문을 사용하되, 처음 i값이 j, k 반복문과 달라야하며 | |
| # 3값을 더한 값이 0이여야 한다. | |
| result = [] | |
| nums.sort() | |
| # 이분탐색 알고리즘 사용 | |
| n = len(nums) | |
| for i in range(n - 2): | |
| lf = i + 1 # 좌 | |
| rf = n - 1 # 우 | |
| if i > 0 and nums[i] == nums[i - 1]: continue | |
| while lf < rf: | |
| tmp = nums[i] + nums[lf] + nums[rf] | |
| # 계산해야 할 값 | |
| if tmp > 0: # 0보다 큼 -> 큰수를 당긴다. | |
| rf -= 1 | |
| elif tmp < 0: # 0보다 작음 -> 작은수를 당긴다. | |
| lf += 1 | |
| else: | |
| idx = [nums[i], nums[lf], nums[rf]] | |
| if idx not in result: result.append(idx) | |
| # 중복되지 않은 경우(이미 리스트에 없는 경우에만 삽입) | |
| lf += 1 # 좌에서 한칸 당기고 | |
| rf -= 1 # 우에서 한칸 당기고 | |
| return result | |
-
주석을 참고하면서 이해를 돕습니다.Permalink
4. 알고리즘 및 해설Permalink
- 이중 반복문을 통해 3값을 더한 값이 0인 경우를 구한다.
- 반복문을 통해 해당 위치 좌우칸을 동시에 비교한다. 이때 while문을 통해 탐색을 진행한다.
- 0보다 크다면 큰 수르 당긴다.
- 0보다 작다면 작은 수를 당긴다.
- 0이라면 idx라는 리스트를 만들어 현재 값과 좌측값 우측값을 넣는다.
- 이때 결과 리스트에 값이 없는 경우에만 결과값에 넣어준다.
- 좌우값을 모두 한칸씩 당기며 재탐색한다.
- 위의 과정을 상위 반복문이 끝나기전까지 반복한뒤 결과값을 출력한다.