专栏首页aCloudDeveloperLeetCode:1_Two_Sum | 两个元素相加等于目标元素 | Medium

LeetCode:1_Two_Sum | 两个元素相加等于目标元素 | Medium

题目:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

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

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2 

函数原型:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    }
};

解题思路:

1、暴力法:两个for循环遍历,时间复杂度为O(N^2),会超时。

2、排序法:这里有两种思路:

  1)排好序后,利用区间法来计算两个数的和(两个指针分别指向首尾,逐步向中间收缩)

  2)排好序后,固定一个元素a[i],在余下的数中查找target - a[i],查找可用二分查找法,时间复杂度为O(lgn)。

该种方法的时间复杂度为O(nlgn)。

注意:这种方法由于采用了排序,故每个数的index会改变,所以,必须将每个数和它的index进行关联,我们第一时间想到map,但是map不允许有重复的元素出现,故不合适。进而可以想到结构体,每个数有两个属性:value和index,这样就搞定了。

3、hashtable法:时间复杂度降为O(N)。思想来自排序法的第一种思路,这种方法用到了查找,总所周知,查找最快的方法就是采用hash表。但是前面也说过,hash不能存储重复的元素,比如(0,3,2,0),只存储3个元素,那查找后就无法得到正确答案。这个时候就需要想一种方法来避免这种情况,我们可以这样来做:来一个元素a[i],我们检查它是否在hash表中,不在就插入,然后检查target-a[i]是否在表中,如果在,得到结果。这样就可以得到我们想要的结果,千万不要把所有元素都插入了,再来查找,不然就得不到答案。

代码展示:

排序法:(第一种思路)

 1 //方法一:排序法
 2 struct SNode {
 3     int value;
 4     int pos;
 5 };
 6 
 7 bool cmp(SNode a, SNode b)
 8 {
 9     return a.value < b.value;
10 }
11 
12 vector<int> twoSum(vector<int>& nums, int target) {
13     int n = nums.size();
14     
15     vector<int> vecRet;
16     vector<SNode> vecNode;
17     
18     for (int i=0; i < n; i ++) {
19         SNode temp;
20         temp.value = nums[i];
21         temp.pos = i+1;
22         vecNode.push_back(temp);
23     }
24     sort(vecNode.begin(),vecNode.end(), cmp);
25 
26     int i = 0, j = n-1;
27     while(i < j) {
28         int sum = vecNode[i].value + vecNode[j].value;
29         if (sum == target) {
30             if(vecNode[i].pos < vecNode[j].pos){
31                 vecRet.push_back(vecNode[i].pos);
32                 vecRet.push_back(vecNode[j].pos);
33                 break;
34             }
35             if (vecNode[i].pos > vecNode[j].pos) {
36                 vecRet.push_back(vecNode[j].pos);
37                 vecRet.push_back(vecNode[i].pos);
38                 break;
39             }
40         }
41         else if (sum > target)
42             j--;
43         else
44             i ++;
45     }
46     return vecRet;
47 }

hashtable法:

 1 //方法二:hashtable法
 2 vector<int> twoSum1(vector<int>& nums, int target) 
 3 {
 4     int i, sum;
 5     vector<int> results;
 6     map<int, int> hmap;
 7     for(i=0; i<nums.size(); i++){
 8         if(!hmap.count(nums[i])){
 9             hmap.insert(pair<int, int>(nums[i], i));
10         }
11         if(hmap.count(target-nums[i])){
12             int j=hmap[target-nums[i]];
13             if(j<i){
14                 results.push_back(j+1);
15                 results.push_back(i+1);
16                 return results;
17             }
18         }
19     }
20     return results;
21 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法导论2-9章补充几道题

    本篇博文意在对前几章中遗漏的,本人觉得有意思的习题当独拿出来练练手。 1、习题2-4,求逆序对,时间复杂度要求Θ(nlgn) 定义:对于一个有n个不同的数组A,...

    CloudDeveloper
  • LeetCode: 106_Construct Binary Tree from Inorder and Postorder Traversal | 根据中序和后序遍历构建二叉树 | Medium

    要求:根据中序和后序遍历序列构建一棵二叉树 代码如下: 1 struct TreeNode { 2 int val; 3 ...

    CloudDeveloper
  • 算法导论第二章小试牛刀

    Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于...

    CloudDeveloper
  • Codeforces Round #513 A. Phone Numbers(水题)

    题目链接:http://codeforces.com/contest/1060/problem/A

    Ch_Zaqdt
  • P1972 [SDOI2009]HH的项链 离线树状数组计数

    对询问按照右端点排序,然后 计算按照树状数组求和计算 l,r = sum(r) - sum(l-1)

    用户2965768
  • Java工具集-数学(阶乘函数)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • 程序员面试50题—栈的应用(7)

    #include<iostream> using namespace std; //void f1(const int& v1,const int& v2) ...

    互联网金融打杂
  • 【每日一练】第001期--两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    会呼吸的Coder
  • LeetCode 136 Single Number

    ShenduCC
  • 105. 从前序与中序遍历序列构造二叉树

    前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:

    祝你万事顺利

扫码关注云+社区

领取腾讯云代金券