编译手艺人

术之尽头

0%

X个数之和系列问题

Posted on Edited on In

从零开始的算法历险 – 0x01

1. 从两数之和(2-Sum)开始

1.1 问题描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

1.2 问题分析

1.3 实现代码

twosum.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> twoSum(vector<int>& numbers,int targets){
    map<int,int> mapping;
    vector<int> result;
    // Map<Value, Index>
    for(int i = 0;i < numbers.size();i++){
        mapping[numbers[i]] = i;
    }

    for(int i = 0; i < numbers.size();i++){
        int searched = targets - numbers[i];
        if(mapping.find(searched) != mapping.end() && i != mapping[searched]){
            result.push_back(i+1);
            result.push_back(mapping[searched] + 1);
            break;
        }
    }
    return result;
}