长春网站建设选择星宿科技,安徽省建设厅到底哪个网站,小学校园网站建设方案工作职责,卫浴洁具公司网站模板这道题目最直接的方法就是for循环俩次遍历数组#xff0c;第二次遍历用target减去对应的值然后看数组中是否有该值#xff0c;这种的解法时间复杂度是O(n^2)。我们想一下之所以需要二次遍历的原因是因为没有办法在O(1)的时间内判断出差值是否存在于该数组中#xff0c;如果有…这道题目最直接的方法就是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) {HashMapInteger,Integer mp new HashMap();for(int i 0;iarr.length;i) {mp.put(arr[i],i);}int[] res new int[2];for(int i 0;iarr.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;}
}
