매일 LeetCode 풀기 | 3Sums

 

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]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.
 
Constraints:
3 <= nums.length <= 3000-105 <= nums[i] <= 105

 

단순무식하게 반복문 3개로 풀긴 풀었지만, 시간초과가 떴다. 반복문말고는 생각나는 접근법이 없었다. 

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var answer: [[Int]] = []
        for i in 0..<nums.count - 2 {
            for k in 1..<nums.count - 1 {
                for t in 2..<nums.count {
                    if i != k && i != t && k != t {
                        if nums[i] + nums[k] + nums[t] == 0 {
                            let array = [nums[i], nums[k], nums[t]].sorted()
                            if !answer.contains(array) {
                                answer.append(array)
                            }
                    }
                    }
                 }
            }
        }
        return answer
    }
}

 

배운 코드 

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var answer: [[Int]] = []
        let array = nums.sorted() 

        for i in 0..<array.count - 2 {
            if i > 0 && array[i] == array[i-1] {
                continue
            }

            var left = i + 1
            var right = array.count - 1

            while left < right {
                let sum = array[i] + array[left] + array[right]

                if sum == 0 {
                    answer.append([array[i], array[left], array[right]])

                    while left < right && array[left] == array[left + 1] {
                        left += 1
                    }

                    while left < right && array[right] == array[right - 1] {
                        right -= 1 
                    }

                    left += 1 
                    right -= 1

                } else if sum < 0 {
                    left += 1
                } else {
                    right -= 1
                }
            }
        }
        
        return answer
    }
}

 

접근 방식 
1. array를 sort한다. 
2. array를 반복문 돌린다. 
4. 지금 인덱스 값의 다음 인덱스 원소와 가장 배열의 가장 끝단에 left, right를 둔다. 
3. 지금 인덱스의 원소가, 바로 이전 원소와 같으면 건너뛴다. 
4-1. sum 이 0이라면, 배열에 append한다 
        array[left] == array[left+1] 일 때까지 left를 오른쪽으로 이동시킨다. 
        array[right] == array[right-1] 일때까지 right를 왼쪽으로 이동시킨다. 
        중복 지점을 찾았으니, 그 지점에서 left와 right를 한 칸씩 이동시켜 새로운 조합을 찾는다. 
4-2. sum이 0보다 작으면, left를 한 칸 옮겨서 좀 더 sum을 크게 만든다. 
4-3. sum이 0보다 크면, right를 한 칸 옮겨서 좀 더 sum을 적게 만든다. 

 

---

투포인터 접근방식 

 

• 정의:
  • 두 개의 포인터를 사용하여 배열이나 리스트를 순회하는 알고리즘 패러다임입니다.
  • 주로 정렬된 배열에서 사용되며, 특정 조건을 만족하는 요소 쌍을 찾는 데 효과적입니다.
• 작동 방식:
  • 보통 하나의 포인터는 배열의 시작, 다른 하나는 끝에서 시작합니다.
  • 두 포인터를 조건에 따라 움직이면서 원하는 결과를 찾습니다.
• 사용 사례:
  • 두 수의 합 문제 (예: 주어진 합을 만드는 두 수 찾기)
  • 세 수의 합 문제 (3Sum)
  • 부분 배열의 합 문제
  • 팰린드롬 확인
• 장점:
  • 시간 복잡도 개선: 대부분의 경우 O(n^2)에서 O(n)으로 줄일 수 있습니다.
  • 공간 효율성: 추가 공간을 거의 사용하지 않습니다 (in-place 알고리즘).
• 핵심 아이디어:
  • 정렬된 데이터의 특성을 활용합니다.
  • 불필요한 조합을 효과적으로 제거합니다.
  • 각 단계에서 검색 범위를 좁혀나갑니다.