[파이썬][Leetcode][릿코드] 3Sum

1. 문제

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. 해결방법 시간복잡도

1. 이분탐색 O(N^2)

3. 문제 해결 및 코드

---

• 주석을 참고하면서 이해를 돕습니다.

4. 알고리즘 및 해설

1. 이중 반복문을 통해 3값을 더한 값이 0인 경우를 구한다.
2. 반복문을 통해 해당 위치 좌우칸을 동시에 비교한다. 이때 while문을 통해 탐색을 진행한다.
   • 0보다 크다면 큰 수르 당긴다.
   • 0보다 작다면 작은 수를 당긴다.
   • 0이라면 idx라는 리스트를 만들어 현재 값과 좌측값 우측값을 넣는다.
     • 이때 결과 리스트에 값이 없는 경우에만 결과값에 넣어준다.
   • 좌우값을 모두 한칸씩 당기며 재탐색한다.
3. 위의 과정을 상위 반복문이 끝나기전까지 반복한뒤 결과값을 출력한다.