[C++] 1. Two sum

문제

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

 

풀이

Brute force

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i) {
            int num1 = nums[i];

            for (int j = i + 1; j < nums.size(); ++j) {
                int num2 = nums[j];
                if (target == num1 + num2)
                    return {i, j};
            }
        }

        return {};
    }
};

time complexity: O(N^2)

space complexity: O(1)

 

 

Hash (Naive)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> h;

        for (int i = 0; i < nums.size(); ++i)
            h[nums[i]] = i;

        for (int i = 0; i < nums.size(); ++i) {
            int num1 = nums[i];
            int num2 = target - num1;
            if (h.find(num2) != h.end() && h[num2] != i)
                return {i, h[num2]};
        }

        return {};
    }

};

time complexity: O(N)

space complexity: O(N)

 

 

Hash

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> h;

        for (int i = 0; i < nums.size(); ++i) {
            int num1 = nums[i];
            int num2 = target - num1;

            if (h.find(num2) != h.end() && h[num2] != i)
                return {i, h[num2]};
            

            h[num1] = i;
        }

        return {};
    }

};

time complexity: O(N)

space complexity: O(N)