[LeetCode] Array > Two Sum

leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/546/

Explore - LeetCode

 

---

풀이

2중 for문을 통해 Brute-Force를 진행하면 해결할 수 있지만, 이를 조금 개선하여 해결

 

배열 내 x, y의 합이 target이 되려면 x를 기준으로 자기 뒤에 target-x라는 수가 존재하면 가능하다는

논리를 가지고 문제를 접근했다.

이렇게 하면 반복되는 계산을 막을 수 있다.

• ex) [2, 7, 11, 15]라는 배열 존재, target = 18
• 1단계 : x =2
  • target을 만족하기위해서 자기 뒤([7, 11, 15])에 16이라는 수가 존재해야함
  • 없으므로 pass
• 2단계 : x =7
  • target을 만족하기위해서 자기 뒤([11, 15])에 11이라는 수가 존재해야함
  • 앞서 1단계에서 2+7의 값이 target이 되는지는 이미 계산했으므로 다시 하지 않아도됨.
  • 뒤에 11이 존재하므로 해당 두 숫자의 index를 찾아서 반환

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        answer = []
        for i,p in enumerate(nums):
            if (target-p) in nums[i+1:]:
                answer.append(i)
                answer.append(i + nums[i+1:].index(target-p) + 1)
        return answer