01 Two Sum

1. Description

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.

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

2. Algorithms

elements	2	7	11	15
index	0	1	2	3

 

iteration	i	j(i+1)	sum	result
1	0(2)	1(7)	9	[0,1]
2	1(7)	2(11)	18
3	2(11)	3(15)	26

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

1. 하나의 리스트에서 두개의 값을 추출하여 조건에 맞는 값의 인덱스를 저장
2. 첫번째 for loop에서 nums[i] 값 추출
3. 두번째 for loop에서 인덱스 i를 제외한 nums[j] 값 추출
4. nums[i] + nums[j] == target일 경우의 인덱스 [i, j] 출력

records_key	2	7	11	15
records_value	0	1	2	3

 

iteration	target	nums[i]	left_over	in records
1	9	i = 0, 2	7	True
2	9	i = 1, 7	2	True
3	9	i = 2, 11	-2	False
4	9	i = 3, 15	-6	False

 

class Solution:
    def twoSum(self, nums : List[int], target: int) -> List[int] : 
        records = {}

        for i in range(len(nums)) : 
            records[nums[i]] = i 

        for i in range(len(nums))  :
            left_over = target - nums[i]
            if (left_over in records) and (records[left_over] != i) :
                return [i, records[left_over]]

1. 두 수의 합은 반드시 리스트 안에 존재하기 때문에 target에서 하나의 값을 뺀 나머지는 반드시 리스트 안에 존재함
2. nums의 값을 key, index를 value에 저장하는 record dictionary 생성
3. target에서 nums[i]를 뺀 값을 left_over저장하고 이 값이 records에 존재하는지 확인
4. leftover이 records에 존재하고, leftover key에 해당하는 index value가 두번째 for loop와 동일하지 않는 경우 결과를 출력

3. Conclusion

• Code 1's Time Complexity : $O(N^2)$
• Code 2's Time Complexity : $O(N)$