#include<iostream>
#include<vector>
#include<map>
using namespace std;
//暴力法，108ms,时间复杂度为O(n2)
vector<int> twoSum(vector<int>& nums, int target) 
{
    vector<int>result(2);
    for (int i = 0;i < nums.size()-1;i++)
    {
        for (int j = i + 1;j < nums.size();j++)
        {
            if (nums[i] + nums[j] == target)
            {
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
    return result;
}
//方法二，8ms
//给定 nums = [2, 7, 11, 15], target = 9
vector<int> twoSum(vector<int>&nums, int target)
{
    map<int, int>tempMap;
    vector<int>result(2);
    for (int i = 0;i < nums.size();i++)
    {
        //处理一组异常数据(3,3) 6,   
        if (target - nums[i] == nums[i])
        {
            //如果所找之数恰好为一半，看前面有没有出现过
            map<int, int>::iterator it = tempMap.find(nums[i]);
            //如果出现过就返回结果
            if (it != tempMap.end())
            {
                result[0] = it->second;
                result[1] = i;
                return result;
            }
        }
        //将数据存入map中
        tempMap[nums[i]] = i;
        map<int,int>::iterator it = tempMap.find(target - nums[i]);
        if ( it!= tempMap.end()&&it->second!=i)
        {
            result[0] = it->second;
            result[1] = i;
            return result;
        }
    }
    return result;
}