LeetCode编程挑战(No.1 Two Sum)

日期:2015年07月03日 作者: 分类:编程 浏览:5002

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.

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

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

思路:

1)遍历数组nums;

2)声明一个map变量,以 target - nums[i] 为键,i 为值存储在map中;

3)当进入下一次遍历时,检查muns[i]是否存在于map中,如果存在,说明当前索引值与map中该键的值所对应的索引值符合条件。

 

代码:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> m;
        vector<int> result;
        // 遍历数组
        for(int i=0; i<nums.size(); i++){
            // 如果没有在map中找到第二个值
            if(m.find(nums[i]) == m.end()){
                // 将第一个值的索引位置存储在第二个的键中
                m[target - nums[i]] = i;
            }else{
                // 如果在map中找到第二个值
                result.push_back(m[nums[i]] + 1);
                result.push_back(i + 1);
                break;
            }
        }
        return result;
    }
};

标签:

除非注明,戊辰人博客文章均为原创,转载请以链接形式标明本文地址

本文地址:https://wanglu.info/2015/07/847.html