增城营销型网站建设,wordpress 竞拍,中企动力销售怎么样,wordpress手机怎么用题目#xff1a;给一个整数数组#xff0c;找到两个数使得他们的和等于一个给定的数 target。 你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。注意事项你可以假设只有一组答案。样例给出 numbers [2, 7, 11…题目给一个整数数组找到两个数使得他们的和等于一个给定的数 target。 你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。注意事项你可以假设只有一组答案。样例给出 numbers [2, 7, 11, 15], target 9, 返回 [0, 1].
1.暴力搜索复杂度为O(n2)
class Solution {
public:
/*
* param numbers: An array of Integer
* param target: target numbers[index1] numbers[index2]
* return: [index1 1, index2 1] (index1 index2)
*/vectorint twoSum(vectorint numbers, int target)
{ // write your code here vectorint idx(2);//申请一个大小为2的容器存放下标 for(int i0; inumbers.size(); i) { for(int jnumbers.size()-1; j0; j--) { if(numbers[i]numbers[j]target i!j) { idx[1] i; idx[0] j; } } }if(idx[0]idx[1])//交换两数 { idx[0] idx[0]^idx[1]^idx[0];//方法错误输出的都是0 idx[1] idx[0]^idx[1]^idx[1];}return idx;}
}; 注意上述交换两数的方法输出的都是0 2、哈希表复杂度为O(n) 原理基本原理创建一个hashmap先把所有的值存在hashmap中其中关键字key是元素的值value为对应元素的下标。待查找的关键字为target - nums[i]遍历数组直到找到则返回其在数组中的下标。时间复杂度为O(n)。
class Solution {
public:/** param numbers : An array of Integer* param target : target numbers[index1] numbers[index2]* return : [index11, index21] (index1 index2)*/vectorint twoSum(vectorint nums, int target) {// write your code hereint size nums.size();int i 0;vectorint result;//这里不能定义长度为2否则会输出四个数if(size 2) //判断是否为空{return result;}mapint, int hashMap;//创建一个mapkey是元素的值value是元素原来的下标for(i0; isize; i) {hashMap.insert(pairint, int(nums[i], i));//把所有的元素值和下标插入到map}for(i0; isize; i) {int temp target - nums[i];if (hashMap.count(temp)!0 hashMap[temp]!i) //hashMap.count(temp)是temp在表中出现的次数{result.push_back(i);result.push_back(hashMap[temp]);break;//只要找到就跳出循环}}if(result[0] result[1]) //调整大小顺序{int temp result[0];result[0] result[1];result[1] temp;}return result;}
}; 参考1.https://www.cnblogs.com/libaoquan/p/6808064.html 2.http://blog.csdn.net/kkdd2013/article/details/51953035
