leetcode02－Two Sum

这道题目最直接的方法就是for循环俩次遍历数组，第二次遍历用target减去对应的值然后看数组中是否有该值，这种的解法时间复杂度是O(n^2)。我们想一下之所以需要二次遍历的原因是因为没有办法在O(1)的时间内判断出差值是否存在于该数组中，如果有的话其实遍历一次数组就可以了，O(1)时间复杂度判断一个数字是否存在？没错，有现成的数据结构能够满足我们的诉求，用map

import java.util.HashMap;
public class twoSum{
public static void main(String[] args) {
int[] arr = {2,7,11,15};
int[] brr = getIdx(arr,9);
if(brr.length > 0) {
System.out.println(brr[0]);
System.out.println(brr[1]);
}
}
public static int[] getIdx(int[] arr,int target) {
HashMap<Integer,Integer> mp = new HashMap();
for(int i = 0;i<arr.length;i++) {
mp.put(arr[i],i);
}
int[] res = new int[2];
for(int i = 0;i<arr.length;i++) {
if(mp.containsKey(target-arr[i]) && i != mp.get(target-arr[i])) {
res[0] = i;
res[1] = mp.get(target-arr[i]);
return res;
}
}
return res;
}
}

原文地址：https://blog.csdn.net/wellwang1993/article/details/136994257

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！