[LeetCode] 1. Two Sum c++

문제 설명

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.

제한 사항

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

입출력 예

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

풀이

주어진 nums배열에서 두개의 원소의 합이 target과 같게 되는 index를 반환하는 문제이다.

 

two point를 사용하기 위해 이중 for문을 사용하였다.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        for(int i = 0; i < nums.size() - 1; i++){
            for(int j = i + 1; j < nums.size(); j++){
                if(nums[i] + nums[j] == target){
                    result.push_back(i);
                    result.push_back(j);
                }
            }
        }
        return result;
    }
};

 

다른 방법

unordered map을 사용하니 runtime이 확실히 줄었다.

두개의 원소를 찾아서 더하는 방법이 아닌 target - nums[i] 식을 사용했다.

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