企业官网建设流程全解析

问题描述: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.
给定一个数组和一个目标值,找到两个数组相加的和为目标值.只有一个解,不能够使用两次相同的元素.

LZ的想法比较简单,两次循环,好暴力…

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> indice_a; for(int i = 0; i<nums.size()-1; i++){ for(int j = i+1; j<nums.size(); j++){ if(nums[i]+nums[j]==target) { indice_a.push_back(i); indice_a.push_back(j); break; } } } return indice_a; } };

结果测试时间是216ms!

为了减少runtime,也即时间复杂度

使用哈希表,只要10ms!

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { std::unordered_map<int, int> mp; std::vector<int> ans; // 用哈希表来做 for(int i = 0; i < nums.size(); i ++) // 对于数组中的每个数据 { // 判断target - numbers[i]在不在 if(mp.count(target - nums[i])) // 如果在里面 { // 那么numbers中就存在两个数和为target ans.push_back(mp[target - nums[i]] ); ans.push_back(i ); break; } if(mp.count(nums[i]) != 1) { mp[nums[i]] = i; } } return ans; } };

代码的魅力在于此^_