LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 정수 배열 nums, 정수 target
2. output: nums의 서로 다른 idx의 4개의 수를 합하여 target을 만들 수 있는 모든 경우 배열로 리턴
   • 1 <= nums.length <= 200
   • 10^9 <= nums[i] <= 10^9
   • 10^9 <= target <= 10^9

Idea

해당 문제를 완전탐색으로 풀 경우, O(n^4)로(16억회) 시간초과

대략 O(n^2)이나 O(n^3)으로 풀어야 통과가 될 것이다.

3Sum문제에서 하나의 숫자를 고정한 후 투포인터로 푸는 방식을 사용하여 O(n^3)을 O(n^2)로 만들었었다. 동일한 방식으로 두개의 숫자를 고정한 후 투포인터로 해당 문제를 O(n^3)으로 해결할 수 있다. → Sol1

Solution

1. 투포인터

   2개의 숫자를 완전탐색으로 고정 후, 투포인터 ⇒ O(n^4) → O(n^3)

   class Solution {
       fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
           nums.sort()
           var result = mutableListOf<List<Int>>()
           // 완전탐색으로 2개의 숫자 고정 (가장 작은 값과 가장 큰값으로 고정)
           for (i in 0 until nums.size - 1) {
               for (j in i + 1 until nums.size) {
                   // 절대 target을 만들 수 없는 경우 continue
                   if ((target > 0 && nums[j] < 0) || (target < 0 && nums[i] > 0)) continue
                   if (j - i > 2) { // 고정한 두 개의 값 사이에 투포인터가 위치할 수 있는 경우
                       var subTarget: Long = target.toLong() - nums[i] - nums[j]
                       var left = i + 1
                       var right = j - 1
                       // 절대 target을 만들 수 없는 경우 continue
                       if ((subTarget > 0 && nums[right] < 0) || (subTarget < 0 && nums[left] > 0)) continue
                       while (left < right) { // 투포인터 탐색
                           if (nums[left].toLong() + nums[right] == subTarget) {
                               result.add(listOf(nums[i], nums[left], nums[right], nums[j]))
                           }
                           if (nums[left] + nums[right] < subTarget) left++ else right--
                       }
                   }
               }
           }
           return result.distinct() // 중복 제거
       }
   }
   

   시간 복잡도: 배열 이중 순회 X (투포인터) = n^3

   

```kotlin

```

시간 복잡도: 

Point

1. 유사 문제: 3개의 숫자의 합 문제