leetCode 1. Two Sum 数组

1. Two Sum

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].

题目大意：

在一个数组中找出2个元素的和等于目标数，输出这两个元素的下标。

思路：

最笨的办法喽，双循环来处理。时间复杂度O(n*n)。

代码如下：

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

参考他人的做法：https://discuss.leetcode.com/topic/3294/accepted-c-o-n-solution

采用map的键值，把元素做键，把元素的下标做值。

vector twoSum(vector &numbers, int target){    //Key is the number and value is its index in the vector.    unordered_map hash;    vector result;    for (int i = 0; i < numbers.size(); i++) {        int numberToFind = target - numbers[i];            //if numberToFind is found in map, return them        if (hash.find(numberToFind) != hash.end()) {                        result.push_back(hash[numberToFind]);            result.push_back(i);                        return result;        }            //number was not found. Put it in the map.        hash[numbers[i]] = i;    }    return result;}

2016-08-11 15:02:14