问题描述：
给定一个整数数组，返回两个数字的索引，使它们相加的值等于一个特定的目标值。假设对于每个输入只有一种解决方案，并且您不可以两次同时使用相同的元素。
问题的示例：
给定nums = [2,7,11,15]， target = 9，
因为nums[0] + nums[1] = 2 + 7 = 9，返回[0,1]。
要求：算法时间复杂度为n
public class TwoSum { public static void main(String[] args) { int[] arr= {1,2,3,4,5,6,7,8,9}; int target=8; List re=twoSum1(arr,target); for(Object ob:re) { System.out.println(ob.toString()); } } //暴力解决方式,空间复杂度为数组的长度n,时间复杂度为n*n public static List twoSum1(int[] arr,int target) { List al=new ArrayList(); for(int i=0;i<arr.length;i++) { for(int j=i+1;j<arr.length;j++) { if(target==arr[i]+arr[j]) { String str=i+"-"+j; al.add(str); } } } return al; } //两遍哈希表 //空间换时间,让时间复杂度为n,那么找到需要的元素只能使用1 //此题的空间复杂度为n，时间复杂度为n public static List twoSum2(int[] arr,int target) { List list=new ArrayList(); //1.将数组中的元素使用hashMap的方式存储 Map map=new HashMap(); for(int i=0;i<arr.length;i++) { map.put(arr[i], i); } for(int i=0;i<arr.length;i++) { int aaa=arr[i]; int bbb=target-aaa; if(map.containsKey(bbb) && (int)map.get(bbb)>i) { list.add(i+"-"+map.get(bbb)); } } return list; } }
