LeetCode: 1. Two Sum

위 문제는 다양한 방식으로 풀이가 가능하다.

nums의 최대크기가 1000이기 때문에 브루트포스도 가능하지만

시간복잡도를 생각하면 O(n)방식으로 푸는 것이 가장 현명해보인다.

 

1. Brute Force방식

시간복잡도 : O(n^2)

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

 

2. Map사용

시간복잡도 : O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> m;
        vector<int> ans;
        for(int i=0; i<nums.size(); i++){
            m[nums[i]] = i;
        }
        
        for(int i=0; i<nums.size(); i++){
            int temp = target-nums[i];
            if(m.count(temp)==0) continue;
            if(i==m[temp]) continue;
            ans.push_back(i);
            ans.push_back(m[temp]);
            
            break;
        }
        
        return ans;
    }
};