LeetCode 솔루션 분류
[Easy - wk1 - Q1] 1. Two Sum
본문
이번주부터 새로 시작하는 Easy 문제입니다. 문제는 주중 매일 1개씩 매주 5개로, Top interview Questions로 시작하겠습니다.
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.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
태그
#leetcode, #문제풀이, #easy, #amazon, #adobe, #google, #apple, #microsoft, #facebook, #bloomberg, #uber, #expedia, #spotify, #goldman sachs, #oracle, #morgan stanley, #yahoo, #paypal, #walmart global tech, #visa, #dell, #ibm, #zoho, #jpmorgan, #intel, #american express, #accenture, #samsung, #intuit, #zillow, #vmware, #s
관련자료
-
링크
댓글 5
yuun님의 댓글
- 익명
- 작성일
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
diff_idx = {}
for idx, num in enumerate(nums):
diff = target - num
if num not in diff_idx:
diff_idx[diff] = idx
else:
return [diff_idx[num], idx]
return []CANUS님의 댓글
- 익명
- 작성일
// Time Complexity: O(n^2)
// Space Complexity: O(1)
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for (idx, num) in nums.enumerated() {
if let idx2 = nums.lastIndex(of: target - num), idx != idx2 {
return [idx, idx2]
}
}
return []
}
}
// Time Complexity: O(n)
// Space Complexity: O(n)
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var buff: [Int: Int] = [:]
for (idx, num) in nums.enumerated() {
if let idx2 = buff[target - num] {
return [idx, idx2]
}
buff[num] = idx
}
return []
}
}
Coffee님의 댓글
- 익명
- 작성일
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0; i<nums.length; i++){
int num2 = target - nums[i];
if(map.containsKey(num2)){
return new int[] { map.get(num2), i };
}
map.put(nums[i], i);
}
return null;
}
}Jack님의 댓글
- 익명
- 작성일
Python
class Solution_1:
def twoSum(self, nums:int, target:int) -> int:
res=[]
for i in range(1,len(nums)):
key=target - int(nums[i-1])
for j in range(i,len(nums)):
if key == nums[j]:
res.append(i-1)
res.append(j)
break
return res
"""
Submissions:
Runtime: 3532 ms, faster than 27.92% of Python3 online submissions for Two Sum.
Memory Usage: 15 MB, less than 76.56% of Python3 online submissions for Two Sum.
"""
class Solution_2:
def twoSum(self, nums:int, target:int) -> int:
dic = {}
for i,num in enumerate(nums):
if num in dic:
return (dic[num],i)
dic[target-num] = i
"""
Submissions:
Runtime: 48 ms, faster than 77.68% of Python3 online submissions for Two Sum.
Memory Usage: 14.4 MB, less than 100.00% of Python3 online submissions for Two Sum.
"""
# Brute-Force
class Solution_3:
def twoSum(self, nums:int, target:int) -> int:
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
"""
Submisstions:
Runtime: 44 ms, faster than 90.36% of Python3 online submissions for Two Sum.
Memory Usage: 14.4 MB, less than 97.59% of Python3 online submissions for Two Sum.
"""
class Solution_4:
def twoSum(self, nums:int, target:int) -> int:
for i , n in enumerate(nums):
complement = target - n
if complement in nums[i+1:]:
return nums.index(n), nums[i+1:].index(complement) + (i+1)
"""
Submissions:
Runtime: 36 ms, faster than 99.36% of Python3 online submissions for Two Sum.
Memory Usage: 14.5 MB, less than 95.86% of Python3 online submissions for Two Sum.
"""
class Solution_5:
def twoSum(self, nums:int, target:int) -> int:
nums_map={}
for i, num in enumerate(nums):
nums_map[num]=i
for i, num in enumerate(nums):
if target - num in nums_map and i != nums_map[target - num]:
return nums.index(num), nums_map[target - num]
"""
Submissions:
Runtime: 52 ms, faster than 54.62% of Python3 online submissions for Two Sum.
Memory Usage: 14.4 MB, less than 96.48% of Python3 online submissions for Two Sum.
"""
class Solution_6:
def twoSum(self, nums:int, target:int) -> int:
nums_map={}
for i, num in enumerate(nums):
if target - num in nums_map:
return [nums_map[target-num], i]
nums_map[num]=i
"""
Submissions:
Runtime: 48 ms, faster than 76.35% of Python3 online submissions for Two Sum.
Memory Usage: 14.4 MB, less than 97.59% of Python3 online submissions for Two Sum.
"""
Chloe님의 댓글
- 익명
- 작성일
class Solution(object):
def twoSum(self, nums, target):
result=[]
for i in range(len(nums)):
for j in range(len(nums)-1):
if i!=j and nums[i]+nums[j]==target:
result=[i, j]
break
return result
