nums 라는 list가 주어졌을 때, 합이 target이 되는 두 수의 index를 출력하는 문제이다.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
보자마자 nums list를 sorting을 해야겠다는 생각이 들었다. 그 후 첫번째(가장 작은 수)와 마지막번째(가장 큰 수)를 시작을 해서 점점 중앙으로 범위를 좁히면 어떨까 생각을 해보았다.
즉 i=0, j=len(nums)-1 로 초기화를 한 후 nums[i] + nums[j]가 target 보다 작으면 i를 증가, targer 보다 크면 j를 감소 시키는 방법이다.
하지만 nums 리스트의 index를 return 해야하기 때문에
new_nums = [(nums[i], i) for i in range(len(nums))]
위 코드와 같이 기존 index를 정보를 갖고 있는 new_nums 리스트를 만든 후 진행하였다.
전체 코드는 아래와 같다. Runtime은 적당히 나왔지만, new_nums를 만들었기 때문에 Memory는 꽤 차지를 하였다.
def twoSum(self, nums: List[int], target: int) -> List[int]:
new_nums = [(nums[i], i) for i in range(len(nums))]
new_nums.sort(key=lambda x:x[0])
i = 0
j = len(nums)-1
while(True):
now_sum = new_nums[i][0] + new_nums[j][0]
if now_sum < target:
i = i + 1
if now_sum > target:
j = j - 1
if now_sum == target:
return [new_nums[i][1], new_nums[j][1]]