LeetCode1. Two Sum（思维）

Easy
Accepted：1,361,010
Submissions：3,401,064

Description

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] + nums[1] = 2 + 7 = 9,
return [0, 1].

链接

https://leetcode.com/problems/two-sum/

题意

给定一个数组a[]和一个目标值t，返回两个数的索引i和j使得a[i]+a[j]=t。保证答案唯一且一个数最多只能使用一次。

思考

如果直接暴力的话，两层循环就可以完成，时间复杂度$O(n^2)$
考虑优化，拿空间换时间，遍历一次数组就能解决问题。在遍历的过程中，对于某个数a[i]，看另一个数t-a[i]是否存在数组中即可（注意两个数的下标不同），可以使用map来存储数值和键值对之间的映射关系，实际上我们用的是unordered_map，因为对于查找问题，unordered_map会更加高效一些，查找操作为常数时间复杂度
（2019年2月3日），使用unordered_map的话，会有一个bug，对{3,2,3,1,3}, 6时，结果为0, 4，unordered_map保存的是重复元素中最后一个的位置，但是因为题目保证答案唯一，所以我们恰好避免了这种情况

代码

Runtime: 4 ms, faster than 99.95% of C++ online submissions for Two Sum.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> ump;
        vector <int> ans;
        int len = nums.size(), tmp;
        for (int i = 0; i < len; ++i) // 建立映射关系
            ump[nums[i]] = i;
        for (int i = 0; i < len; ++i)
        {
            tmp = target - nums[i];
            if (ump.count(tmp) && ump[tmp] != i) // 存在target-a[i]且不为同一个数
            {
                ans.push_back(i);
                ans.push_back(ump[tmp]);
                break;
            }
        }
        return ans;
    }
};

话说这种写法有些不习惯。还有一个问题是我在找到答案后直接返回会报错warning: control reaches end of non-void function，意思是一些本应带有返回值的函数到达结尾后可能并没有返回任何值，所以还是得在最后返回。

拓展

还有一种更高效的写法，来自于Grandyang大佬，现在知道了返回空时直接return {}就行。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            if (m.count(target - nums[i])) {
                return {i, m[target - nums[i]]};
            }
            m[nums[i]] = i;
        }
        return {};
    }
};

还有一个神仙操作是$O(n^2)$的暴力代码也能过，膜拜一下大脸喵。

vector<int> twoSum(vector<int> &numbers, int target) {
    int n = numbers.size();
    vector<int> result;
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(numbers[i] + numbers[j] == target)
            {
                result.push_back(i);
                resul.push_back(j);
                return result;
            }
        }
    }
}

参考

Grandyang：LeetCode All in One 题目讲解汇总(持续更新中...)
BillCYJ：map和unordered_map的差别和使用
qtyl1988：warning: control reaches end of non-void function

The end.
2019年1月26日星期六