给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。
(注:返回的数组下标从1开始算起,保证target一定可以由数组里面2个数字相加得到)
要求:空间复杂度 O(n)O(n),时间复杂度 O(nlogn)O(nlogn)
输入:
[3,2,4],6
返回值:
[2,3]
说明:
因为 2+4=6 ,而 2的下标为2 , 4的下标为3 ,又因为 下标2 < 下标3 ,所以返回[2,3]
输入:
[20,70,110,150],90
返回值:
[1,2]
说明:
20+70=90
如果用两个for循环 由于限定时间是1s 会超时 所以在此只用一个for循环 并且利用hashmap的性质 进行解题
import java.util.*;
public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
int numbers_len = numbers.length;
int[] res = new int[2];
HashMap<Integer,Integer> hm = new HashMap<Integer, Integer>();
for(int i =0; i < numbers_len; i++){
if(hm.containsKey(target - numbers[i])){
res[0] = hm.get(target - numbers[i]) + 1;
res[1] = i + 1;
break;
}else{
hm.put(numbers[i], i);
}
}
return res;
}
}
标签:下标,target,int,Jan,NC61,numbers,数组,hm,两数
From: https://www.cnblogs.com/rickierun/p/17058604.html