Leet me code 1 - [LeetCode][C++] 1. Two Sum (Easy)

Leet me code :-P

 

---

https://leetcode.com/problems/two-sum/

Two Sum - 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.

---

문제 정리

- Input 
nums : 정수 array, 2 <= nums.length <= 104, 109 <= nums[i] <= 109
target : 정수, -109 <= target <= 109

- Output : nums 두 정수를 더한 값이 target이 되는 두 인덱스 값 반환

 

생각의 흐름

두 정수를 x, y라 하면 target = x + y, y = target - x

nums를 순회하면서 target - x 값과 x값의 인덱스를 map에 저장하고,

다음으로 nums를 순회할 때, nums[y]가 map에 있는지 확인

!!! 놓친 조건 -> nums의 같은 element가 두 번 사용될 수 없다

 

 

Solution 코드 ver. 1

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> list;
        for (int i = 0; i < nums.size(); ++i) {
            list[target-nums[i]] = i;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            if (list.find(nums[i]) != list.end() && list[nums[i]] != i) {
                return {list[nums[i]], i};
            }
        }
        
        return {};
    }
};

 

코드 ver.2

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> list;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = list.find(nums[i]);
            if (it != list.end() && i != it->second) {
                return {it->second, i};
            }
            list[target-nums[i]] = i;
        }
        
        return {};
    }
};