方法一、直接两层for遍历
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] ret=new int[2];
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
ret[0]=i;
ret[1]=j;
return ret;
}
}
}
return null;
}
}
方法二、哈希表
哈希表是根据key和散列函数直接得到存储位置的一种数据结构。
这个解法就是逐个把数放进去,一边放一边检测target-这个数在哈希表中是否存在。由此达到O(N)复杂度。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> hashtable=new HashMap<Integer,Integer>();
for(int i = 0;i < nums.length;i++){
if(hashtable.containsKey(target-nums[i])){
return new int[]{hashtable.get(target-nums[i]),i};
}
hashtable.put(nums[i],i);
}
return null;
}
}
注意HashMap的创建:Map<Integer,Integer> hashtable=new HashMap<Integer,Integer>();
使用:get,put,containsKey