Two Sum

Description

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.

Notice
You may assume that each input would have exactly one solution

Example
numbers=[2, 7, 11, 15], target=9
return [1, 2]

Challenge
Either of the following solutions are acceptable:
O(n) Space, O(nlogn) Time: sort then compare O(n) Space, O(n) Time: hash table

Link

Lintcode_ladder

Method

1. use hash table record all value,
   then scanning hash table with Target to find the second value
2. Sort the whole vector,
   then from the sum = start + end finding the target,
   if sum > target, end--
   if sum < target, start++
   if sum == target, well done

Also, if no requirement for avoiding modification of nums vector, we can use S(1) space

Example

1. 1

class Solution {
public:
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1+1, index2+1] (index1 < index2)
     */
    vector<int> twoSum(vector<int> &nums, int target) {
        // write your code here
        if (nums.empty()) {
            return {};
        }
        int n = nums.size();
        // value index
        unordered_map<int, int> dict;
        for (int i = 0; i < n; ++i) {
            dict[nums[i]] =i;
        }
        for (int i = 0; i < n; ++i) {
            int rest = target - nums[i];
            if (dict.find(rest) != dict.end()) {
                return {i+1, dict[rest]+1};
            }
        }
        return{};
    }
};

Similar problems

x

Tags

x