LeetCode——TwoSum
2024-10-18 12:03:00
题目:
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
我的解法:
public class Solution {
public int[] twoSum(int[] numbers, int target) {
int [] re=new int[2];
int len=numbers.length;
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
if(numbers[i]+numbers[j]==target){
re[0]=i+1;
re[1]=j+1;
}
}
}
return re;
}
}
系统给出结果:
Time Limit Exceeded
显然系统无法忍受我时间复杂度为O(n^2)的时间复杂度。
在讨论版看到一个复杂度为O(n)的算法:
import java.util.Hashtable;
public class Solution {
public int[] twoSum(int[] numbers, int target) {
int [] re=new int[2];
Hashtable<Integer,Integer> hashtable=new Hashtable<Integer,Integer>();
int len=numbers.length;
for(int i=0;i<len;i++){
Integer n=hashtable.get(numbers[i]);
if(n==null) hashtable.put(numbers[i],i);
n=hashtable.get(target-numbers[i]);
if(n!=null&&n<i){
re[0]=n+1;
re[1]=i+1;
return re;
} }
return re;
}
}
最新文章
- 我为Net狂 ~ 社交平台系列小集合!
- Image放大缩小在放进Imageview
- SPSS数据分析—Probit回归模型
- CSS中的::after ::before
- MySQL的Incorrect string value错误
- JAVA中的单利
- 14. javacript高级程序设计-表单
- sourcetree使用问题汇总
- 用Dalvik指令集写个java类
- [原]Unity3D深入浅出 - 常见三维软件与Unity3D的单位比例
- [五]SpringMvc学习-Restful风格实现
- 使用socket.io打造公共聊天室
- OSChina 其中很重要的一类——RequestContext
- 编程乐趣:C#获取日期所在周、月份第一和最后一天
- Activiti工作流入门
- H(X|Y)的推到过程
- Unity协程的坑
- linux下用户操作
- Java装饰者模式
- sqlserver2008 链接服务器 2000