[LeetCode] 1. Two Sum

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]
Explanation: 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.

---

정수 숫자의 배열과 정수 대상이 주어지면, 두 숫자의 합이 타겟과 같도록 반환해야한다.

간단히 생각한다면 2중 for문을 돌며 배열의 i번째와 j번째 값의 합이 target이 되는 것을 찾으면된다.

class Solution:
   def twoSum(self, nums, target):
       for i in range(0, len(nums)):
           for j in range(i+1, len(nums)):
               if nums[i] + nums[j] == target:
                   return [i, j]

이 구조의 시간복잡도는 O(n2)이며, 공간 복잡도는 O(1) 이다.

dictionary를 사용한다면 시간 복잡도, 공간 복잡도를 O(n)이 되는 방식으로도 짤 수 있다.

 

 

 

문제 출처 : https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

Github : https://github.com/kkkkang1009/leetcode/blob/master/leetcode_1.py

GitHub - kkkkang1009/leetcode: leetcode