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 条评论
登录 后参与评论

相关文章

来自专栏前端儿

表达式求值(1)

Dr.Kong设计的机器人卡多掌握了加减法运算以后,最近又学会了一些简单的函数求值,比如,它知道函数min(20,23)的值是20 ,add(10,98) 的值...

1772
来自专栏有趣的Python

1-Java面向对象-面向对象

通过前面的学习我们对于java的语法结构有了一定的认识,掌握了分支结构,循环结构等常用的程序逻辑,也能运用这些知识解决一些简单问题。

2631
来自专栏智能算法

程序员必须了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List...

1160
来自专栏前端吧啦吧啦

涨薪必备Javascript,快点放进小口袋!

1392
来自专栏从流域到海域

Python基本数据类型

其实之前有一篇博客:C\C#\Java\Python 基本数据类型比较 https://cloud.tencent.com/developer/article...

2186
来自专栏mini188

java中的字符串相关知识整理

字符串为什么这么重要 写了多年java的开发应该对String不陌生,但是我却越发觉得它陌生。每学一门编程语言就会与字符串这个关键词打不少交道。看来它真的很重要...

2147
来自专栏web前端教室

不学不知道,sort()方法中的坑

今天的前端零基础课,在讲到js中的sort()排序方法的时候,说sort()这个方法在给数字排序的时候,根本不是按数字大小来排序的。 它是把数字都当成字符串来看...

18710
来自专栏web编程技术分享

【干货】用大白话聊聊JavaSE — ArrayList 深入剖析和Java基础知识详解(二)1. 新建一个MyList类2. 构造函数设计3. add方法实现4. remove方法实现

3096
来自专栏用户2442861的专栏

C++ string中的几个小陷阱,你掉进过吗?

http://blog.csdn.net/lanxuezaipiao/article/details/24885811

1192
来自专栏xx_Cc的学习总结专栏

iOS-正则表达式的简单使用

4167

扫码关注云+社区

领取腾讯云代金券