Leetcode1. Two Sum

ddddLeetcode刷题

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums1 = 2 + 7 = 9,
return [0, 1].

我的代码：暴力法，O(n^2)

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-1
//T(n)=O(n^2), S(n)=O(1)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //如果nums为空，返回空vector<int>对象
        if (nums.empty()) return vector<int>();
        //暴力法
        for(decltype(nums.size()) indexi = 0; indexi < nums.size(); ++indexi)
            for(decltype(nums.size()) indexj = indexi + 1; indexj< nums.size(); ++indexj)
            {
                if(nums[indexi] + nums[indexj] == target)
                    return vector<int>({indexi, indexj});
            }
    }
};

• 分析太简单了，主要是两个循环那里，indexj=indexi + 1;，因为两个数不能是同一下标。

优秀代码：hash，O(n)

• 第三个思路可以想一想，以后没准能用上。因为是排好序的，所以夹逼时：若两数之和大于target，则右侧左移；反之，左侧右移。直至找到解。

hash法：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //如果nums为空，返回空vector<int>对象
        if (nums.empty()) return vector<int>();
        //hash
        unordered_map<int, int> mapping;
        for(decltype(nums.size()) index = 0; index < nums.size(); ++index)
            mapping[nums[index]] = index;
        for(decltype(nums.size()) index = 0; index < nums.size(); ++index)
        {
            auto gap = target - nums[index];
            if(mapping.find(gap) != mapping.end() && mapping[gap] != index)
                return vector<int>({index, mapping[gap]});
        }
    }
};

• 这是非常大气的一段代码，使用了classtype()的方式返回临时对象，使用初值列表{}，使用decltype，使用auto，完全符合C++11标准！高明！