LeetCode两数之和

给定一个整数数列，找出其中和为特定值的那两个数。

class Solution {
    public int[] twoSum(int[] nums, int target) {
             TreeMap<Integer,Integer> map=new TreeMap<>();//hashmap都可以
        for(int i=0;i<nums.length;i++){
            map.put(target-nums[i],i);
        }
        LinkedHashSet<Integer> arr=new LinkedHashSet();//为了记录结果，因为不知道有多少对，是个不确定的长度，所以用list和set最佳
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                if(map.get(nums[i])!=i){
                  arr.add(i);
                  arr.add(map.get(nums[i]));
                  map.remove(target-nums[map.get(nums[i])]);
                  map.remove(nums[i]);   
                }
                 
            }
        }
         
       int b[]=new int[arr.size()];
        int size=0;
        for (Integer integer : arr) {
			b[size]=integer;
			size++;
		}
       return b; 
    }
}

你可以假设每个输入都只会有一种答案，同样的元素不能被重用。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

    看到这个题我们首先想到的是必须要知道a[i]和目标和的差，这样我们才能找到对应的数。如果这点想到了这个问题就迎刃而解了。

     在这里为了方便检索我使用了集合框架：Map(key,value) 他可以直接根据key来查询对应的value，首先我们要把数组放在map中。其中key=targer-a[i]  valuer=i;

    然后在遍历数组，如果a[j]在Map的key集合中，那么一定有另外一个a[i], 使得 a[i]+a[j]=targer 成立。因为我们在存储a[i]的时候是  map(targer-a[i],i)存入的。

   但是有几点要注意：

    1.防止出现 出现 a[i]+a[i]=targer的情况，即数组中有一个元素为2，targer=4,那么就可能出错，所以要加一个判断防止这样的情况出现

   2.防止重复，在找到一组数的时候觉得要把他们remove掉；

好了下面直接代码伺候：