LeetCode 솔루션

[Easy - wk1 - Q1] 1. Two Sum

Chloe 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.03 14:47

10,347 조회
5 댓글
0 추천
0 비추천
목록 게시글 쓰기

이번주부터 새로 시작하는 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

링크

https://leetcode.com/problems/two-sum/ 1899 회 연결

익명
작성일 2022.05.03 20:14

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 []

익명
작성일 2022.05.03 23:37

// 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 []
    }
}

익명
작성일 2022.05.05 03:43

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;
        
        
    }
}

익명
작성일 2022.05.06 22:00

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.
"""

Python

[code]
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.
"""
[/code]
[code]
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.
"""
[/code]
[code]
# 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.
"""
[/code]
[code]
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.
"""
[/code]
[code]
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.
"""
[/code]
[code]
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.
"""
[/code]

익명
작성일 2022.05.08 19:58

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