首页 > > 程序设计 > C/C++ >

#leetcode刷题之路1-两数之和

2019-02-25 16:09:36来源：博客园阅读 ()

题目：

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

数组至少两个数值

第一反应是用两个for循环，但是这是最简单的思想。

然后再细想，可以在相加之前加上判断，相加的两个数不可以比target大。目前也就想到这里。哈哈，这里想错了，没有想到有负数出现的情况，应该是第二个数必须大于target-第一个数

#include <iostream>
#include<vector>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> ans;
    int len = nums.size();
    if (len <= 1)
    {
        cout << "error" << endl;
        return ans;
    }
    for (int i = 0; i<len; i++)
    {
        int diff = target - nums[i];

        for (int j = i + 1; j<len; j++)
        {
            if (diff <= nums[j])
            {
                if (nums[i] + nums[j] == target)
                {
                    ans = { i, j };
                    return ans;
                }
            }
        }

    }
    return ans;
}


int main() {
    vector<int> nums = { -3, 4, 3, 90 };
    vector<int> ans = twoSum(nums, 0);
    std::cout << ans[0] << ans[1] << std::endl;
    return 0;
}

注：vector 的六种创建和初始化方法

29 / 29 个通过测试用例

执行用时：432 ms

服了。。。。。

向高手们学习：发现他们用了map来提升速度。

注：

关于Vector和Map查找效率的惊人的实际测试结果

Vector与Map表的区别

vector和map的效率简要比较

STL的map和hashmap比较

map和unordered_map的差别和使用

方法二：

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> ans;
    int len = nums.size();
    if (len <= 1)
    {
        cout << "error" << endl;
        return ans;
    }
    unordered_map<int, int> map1;
    for (int n = 0; n<len; n++){
        map1[nums[n]] = n;//key=数组里的数，value=序号
    }

    for (int i = 0; i<len; i++)
    {
        int diff = target - nums[i];

        if (map1.find(diff) != map1.end() && map1.find(diff)->second !=i)
        {
            ans = { i, map1.find(diff)->second };
            return ans;

        }
    }
    return ans;
}

执行用时：20 ms 舒服

方法三：

避免了判断是否和自身相同

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> ans;
    int len = nums.size();
    if (len <= 1)
    {
        cout << "error" << endl;
        return ans;
    }
    unordered_map<int, int> map1;


    for (int i = 0; i<len; map1[nums[i]] = i,i++)
    {
        int diff = target - nums[i];

        if (map1.find(diff) == map1.end() )
            continue;
        ans = { map1.find(diff)->second ,i};


    }
    return ans;
}