题目描述

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

思路

数组中的数据相加要等于target，两个for循环穷举每一种可能

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

            }
        }
        return results;
    }
};

时间复杂度是O（n*n）过不了，所以要降低时间复杂度

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i, j;
        vector<int> results;
        map<int, int> hmap;
        for(i = 0; i < num.size();i++)
        {
            if(!hmap.count(nums[i]))//检查hmap中是否有num[i] 没有的话将num[i] 
            {
                hmap.insert(pair<int,int>(nums[i],i));
            }
            if(hmap.count(target - nums[i]))//如果target - nums[i] 也在hmap中
            {
                int n = hmap[target - nums[i]]//获得这个数的索引
                if(n < i)
                {
                results.push_back(n+1);
                results.push_back(i+1);
                return results;
                }
            }

        }
        return results;
    }
};

将索引和对应的值存到map序列中，然后查找一下target - num[i]是否在序列中，如果在就找到了。遍历的过程中同时查找，时间复杂度O（n）。