leetcode series:Two Sum
题目:
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
题解:
这道题也是比较经典处理数组的,有以下两个思路。
思路1:
利用HashMap,把target-numbers[i]的值放入hashmap中,value存index。遍历数组时,检查hashmap中是否已经存能和自己加一起等于target的值存在,存在的话把index取出,连同自己的index也出去,加1(index要求从1开始)后存入结果数组中返回。如果不存在的话,把自己的值和index存入hashmap中继续遍历。由于只是一遍遍历数组,时间复杂度为O(n)。
代码如下:
public int[] twoSum(int[] numbers, int target) {
int [] res = new int[2];
if(numbers==null||numbers.length<2)
return res;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i < numbers.length; i++){
if(!map.containsKey(target-numbers[i])){
map.put(numbers[i],i);
}else{
res[0]= map.get(target-numbers[i])+1;
res[1]= i+1;
break;
}
}
return res;
}
思路2:
又碰到敏感的关键字array和target,自然而然想到二分查找法。但是这道题不能像传统二分查找法那样舍弃一半在另外一半查找,需要一点点挪low和high指针,所以时间复杂度为O(n)。
首先先将整个list拷贝并排序,使用Arrays.Sort()函数,时间复杂度O(nlogn)
然后利用二分查找法,判断target和numbers[low]+numbers[high]。
target == numbers[low]+numbers[high], 记录copy[low]和copy[high];
target > numbers[low]+numbers[high],说明最大的和最小的加一起还小于target,所以小值要取大一点,即low++;
target > numbers[low]+numbers[high], 说明最大的和最小的加一起大于target,那么大值需要往下取一点,即high--。
再把找到的两个合格值在原list中找到对应的index,返回即可。
总共的时间复杂度为O(n+nlogn+n+n) = O(nlogn)。
代码如下:
public int[] twoSum(int[] numbers, int target) {
int [] res = new int[2];
if(numbers==null||numbers.length<2)
return res; //copy original list and sort
int[] copylist = new int[numbers.length];
System.arraycopy(numbers, 0, copylist, 0, numbers.length);
Arrays.sort(copylist); int low = 0;
int high = copylist.length-1; while(low<high){
if(copylist[low]+copylist[high]<target)
low++;
else if(copylist[low]+copylist[high]>target)
high--;
else{
res[0]=copylist[low];
res[1]=copylist[high];
break;
}
} //find index from original list
int index1 = -1, index2 = -1;
for(int i = 0; i < numbers.length; i++){
if(numbers[i] == res[0]&&index1==-1)
index1 = i+1;
else if(numbers[i] == res[1]&&index2==-1)
index2 = i+1;
}
res[0] = index1;
res[1] = index2;
Arrays.sort(res);
return res;
}
转自:https://www.cnblogs.com/springfor/p/3859618.html
Reference:
http://blog.csdn.net/linhuanmars/article/details/19711387
http://blog.csdn.net/likecool21/article/details/10504885
最新文章
- mysql创建用户及授权相关命令
- Python对整形数字进行加密和解密
- css3基础教程:CSS3弹性盒模型
- form表单中的常用控件
- DHTMLX 前端框架 建立你的一个应用程序 教程(九)--绑定表单Form到表格Grrid中
- facebook分享遇到的错误解决方法
- css3文本效果
- 【Centos】yum安装MySQL
- python no module named _socket 原因
- pythonのdjango CSRF简单使用
- springmvc基础使用配置
- 线程安全-002-多个线程多把锁&;类锁
- 0 or 1(hdu2608)数学题
- php中urlencode()和urldecode()URL编码函数浅析[转]
- UITableView-FDTemplateLayoutCell 学习笔记
- iOS - 音乐播放器需要获取音乐文件的一些数据信息(封装获取封面图片的类)
- Nlog、elasticsearch、Kibana以及logstash在项目中的应用(一)
- hdu1584
- python面试题库——1Python基础篇
- 关于@synchronized 比你想知道的还多