문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Follow-up:

Can you come up with an algorithm that is less than O(n2) time complexity?

Python 풀이

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        output = []
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i==j:
                    continue
                else:
                    if nums[i]+nums[j]==target:
                        output.append(i)
                        output.append(j)
                        return output

생각보다 쉬우면서도 어려웠다. 더 좋은 방법이 분명 있을텐데 아직 찾지 못하였다.

먼저 결과값을 저장할 빈 리스트를 만들어 놓고 주어진 정수들을 하나씩 사용해 보며 문제를 풀었다.

이중 for문을 이용하여 주어진 정수 리스트에서 2개를 선택하여 더해서 target number와 같고 인덱스가 다르면 그 두 인덱스를 출력하면 된다.
if i==j i, j는 정수 리스트의 인덱스로 사용할 변수이고 인덱스가 같으면 안되므로(문제 설명에 명시되어 있음) 같으면 다음 숫자로 넘어간다.
같지 않다면 두 숫자를 더해서 target number와 같은지 확인하고 같다면 두 인덱스 i, j가 답이 된다. output이라는 리스트에 집어 넣고 바로 return을 해줘야 for문을 더 이상 진행하지 않고 끝나게 된다.

Follow - up

시간 복잡도를 O(n2)보다 작게 풀어보라고 한다. 내일 더 풀어보고 solution을 찾지 못하면 다른 분들의 풀이 방법을 참고해야겠다.

현재 나의 풀이의 시간 복잡도는 최악이 O(n2)이다.