十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
1. Two Sum
创新互联建站是一家专业提供三河企业网站建设,专注与成都网站设计、成都网站建设、H5网站设计、小程序制作等业务。10年已为三河众多企业、政府机构等服务。创新互联专业的建站公司优惠进行中。
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.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
题目大意:
在一个数组中找出2个元素的和等于目标数,输出这两个元素的下标。
思路:
最笨的办法喽,双循环来处理。时间复杂度O(n*n)。
代码如下:
class Solution { public: vectortwoSum(vector & nums, int target) { vector result; int i,j; for(i = 0; i < nums.size();i++) { for(j = i+1; j < nums.size();j++) { if(nums[i] + nums[j] == target) { result.push_back(i); result.push_back(j); break; } } } return result; } };
参考他人的做法:https://discuss.leetcode.com/topic/3294/accepted-c-o-n-solution
采用map的键值,把元素做键,把元素的下标做值。
vectortwoSum(vector &numbers, int target) { //Key is the number and value is its index in the vector. unordered_map hash; vector result; for (int i = 0; i < numbers.size(); i++) { int numberToFind = target - numbers[i]; //if numberToFind is found in map, return them if (hash.find(numberToFind) != hash.end()) { result.push_back(hash[numberToFind]); result.push_back(i); return result; } //number was not found. Put it in the map. hash[numbers[i]] = i; } return result; }
2016-08-11 15:02:14