Two Sum

05/27/2016 Array Hash Table

本博客主要基于LeetCode官方题解

Question

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.


Brute Force Way

Result: Accepted Time: 668ms

This way is very simple,Loop through each element and find if there is another value that equals to .

Solution in CPP:

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

Complexity Analysis

  • Time Complexity:
  • Space Complexity:

Binary Search Way

Result: Accepted Time: 12ms

In this way, we use a struct to record the value and its index, and sort the vector. Then we loop through each value and use binary search to find if there is another value that equals to .

class Solution {
    struct node{
        int n,pos;
        bool operator < (const node & rhs) const
        { return this->n < rhs.n;}
        node(int v=0,int idx=0):n(v),pos(idx){}
    };
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<node> tmp(nums.size());
        for(int i=0;i<nums.size();i++)
            tmp[i] = node(nums[i],i);
        sort(tmp.begin(),tmp.end());
        for(auto now = tmp.begin();now != tmp.end(); ++now)
        {
            auto it= lower_bound(tmp.begin(),tmp.end(),node(target - now->n));
            if(now != it && it != tmp.end() && it->n == target - now->n)
                return vector<int>{now->pos,it->pos};
        }
        return vector<int>();
    }
};

Complexity Analysis

  • Time Complexity:
  • Space Complexity:

Two Pointers Way

Result: Accepted Time: 12ms

class Solution {
    struct Node{
        int n,pos;
        Node(int v=0,int idx=0):n(v),pos(idx){}
        bool operator < (const Node & rhs) const
        {   return this->n < rhs.n;}
    };
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<Node> tmp(nums.size());
        for(int i=0;i<nums.size();i++)
            tmp[i] = Node(nums[i],i);
        sort(tmp.begin(),tmp.end());
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int sum = tmp[left].n + tmp[right].n;
            if(sum > target)
                right --;
            else if(sum == target)
                return vector<int>{tmp[left].pos,tmp[right].pos};
            else left ++;
        }
        return vector<int>();
    }
};

Complexity Analysis

  • Time Complexity:
  • Space Complexity:

Two-Pass Hash Table

Result: Accepted Time: 20ms

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        int index = 0;
        for(const auto & x:nums)
            mp[x] = index++;
        index = 0;
        for(const auto & x:nums)
            if(++index && mp.count(target-x) && mp[target-x]!=index-1)
                return vector<int>{index-1,mp[target-x]};
        return vector<int>();
    }
};

Complexity Analysis

  • Time Complexity:
  • Space Complexity:

One Pass Hash Table

Result: Accepted Time: 20ms

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        int index = 0;
        for(const auto & x:nums){
            if(mp.count(target-x))
                return vector<int>{index,mp[target-x]};
            mp[x] = index++;
        }
        return vector<int>();
    }
};

Complexity Analysis

  • Time Complexity:
  • Space Complexity: