频道栏目
首页 > 考试 > 其他 > 正文

leetcode - 1 two sum

2017-01-16 10:06:10         来源:laeen的博客  
收藏   我要投稿

tow sum

Given an array of integers,return indices of the two numbers such that they addup to a specific target.

You may assume that each input would have exactly one solution.

给定一个数组,再给定一个目标值,返回数组中的两个下标。

下标i,j满足a[i] + a[j] = target ,其中target为目标值。

第一次思路:

复杂度为O(n^2),在N个选择中挑选两个,一共有n(n-1)/2种选择

class Solution {

public:

    vector<int>twoSum(vector<int>& nums, int target) {

        int i,j;

        vector <int> result;

        int sum = 0;

        int s = nums.size();

        for(i = 0 ; i < s ; i++)

            for(j = i + 1; j < s ; j++){

                sum = nums[i] + nums[j];

                if(sum == target){

                    result.push_back(i);

                    result.push_back(j);

                    break;

                }

            }

        return result;   

    }

};

第二次改进算法:

利用map来改进。

因为在map中查找一个数字的代价为O(1),然后遍历两次数组,第一次遍历是存储键值对,第二次是查找符合标准的两个数字。

其中,第一次遍历需要注意map的一个特性,就是不允许重复的键值,所以为了防止

2 * key = target 这样的情况出现而找不到解,所以需要在放入键值的时候就判断一下。

之后的遍历就是通过两个迭代器来找到符合标准的下标了。

map<int,int> mymap;

                   pair<int,int> p;

                   vector<int>v;

                   map<int,int>::iteratorit;

                   map<int,int>::iteratorit1;

 

                   ints = nums.size();

                  

                   for(inti = 0 ; i < s ; i++){

                            p.first= nums[i];

                            p.second= i;

                            if(mymap.count(p.first))

                                     if(target== 2 * p.first){

                                               it= mymap.find(p.first);

                                               v.push_back((*it).second);

                                               v.push_back(p.second);

                                               returnv;

                            }       

                            mymap.insert(p);

                   }

                           

                   for(it= mymap.begin(); it != mymap.end(); it++){

                            intr = target - (*it).first;          

                            it1= mymap.find(r) ;

                            if(it1!= mymap.end()){

                                     v.push_back((*it).second);

                                     v.push_back((*it1).second);

                                     break;

                                    

                            }

                   }

         returnv; 

    }
上一篇:LeetCode OJ-74.Search a 2D Matrix
下一篇:leetcode 448
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站