Leetcode 1 Solution

This article provides solution to leetcode question 1 (two-sum)
Categories:
Tags:
Access this page by simply typing in "lcs 1" in your browser address bar if you have bunnylol configured.

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

Thinking Process

This is a very easy question. To check if any of the two numbers can be added up to target, we just need to check if target - num exists in the array for each num in the array.

To check if an element is in a data set, we’ll leverage hashmap.

Time & Space Complexity

Assuming N is the size of the array, the time & space compelxities are:

  • Time complexity: O(N)
  • Space complexity: O(N)

Solution

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

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

        for (int i = 0; i < nums.size(); i++)
        {
            if (p.find(target - nums[i]) == p.end())
                continue;

            int other = p[target - nums[i]];

            if (i == other)
                continue;

            return {i, other};
        }

        return {};
    }
};