LC1.两数之和

查看题目

这个问题很容易想到的想法是暴力(作为leetcode对于第一个问题，暴力解决方案并非不可能），但最好的方法是使用哈希表（因为我们需要快速判断是否有符合要求的值），并尽量不要使用它set原因如下：

• 数组的大小是有限的，如果元素很少，哈希值太大，就会浪费内存空间。
• set是一个集合，里面的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下表位置，因为要返回x 和 y下表set 也不能用。 主要思路如下：
• 使用HashMap存储，将target - nums[i]作为key，将i(索引)作为value，至关重要的是，如果你把i作为一个索引，因为你不能根据值搜索索引。key那么就不能直接找到符合要求的了value所对应的key了。
• 遍历数组，每次使用一次map.contains(target - num[i])判断一下map是否与当前值和谐？target如果有，这个时候以i为元素a[1](作为a[0]也可以，没有顺序限制)，使用，map.get(target - nums[i])获得互补价值value，也就是说，这个索引值对应于数组中的索引值a[0]。
• 最后返回a数组。

class Solution { 
             public int[] twoSum(int[] nums, int target) { 
                 int left = 0;         int right = nums.length - 1;         int[] a = new int[2];         Map<Integer,Integer> map = new HashMap<>();         for(int i = 0; i < nums.length; i ){ 
                     int temp = target - nums[i];             if(map.containsKey(temp)){ 
                         a[1] = i;                 a[0] = map.get(temp);
                return a;
            }
            else { 
        
            map.put(nums[i] , i);
            }   
        }
        return a;
    }
}