题目

• 给定一个整数数组 nums 和一个整数目标值 target，
• 请你在该数组中找出 和为目标值 target 的那 两个 整数，
• 并返回它们的数组下标。

示例

• 示例1

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

• 示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

• 示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

代码

解法：使用 HashMap

public int[] twoSum(int[] nums, int target){

    int rt[] = new int[2];
    //k：值，value:索引
    Map<Integer,Integer> hashtable = new HashMap<Integer,Integer>();
    for(int i=0;i<nums.length;i++){
        hashtable.put(nums[i],i);
    }

    for(int i=0;i<nums.length;i++){
        Integer nextIndx = hashtable.get(target - nums[i]);
        if(nextIndx!=null && nextIndx!=i){
            rt[0]=i;
            rt[1]=nextIndx.intValue();
        }
    }
    return rt;   
}

代码分析：1、先把 nums 数组中对应的元素 [值，下标] 存到 HashMap
2、通过在 HashMap 中查找 target - nums[i] ，来找到能构成 nums[i] + nums[j] = target 的值
3、nextIndx != i ：保证查到的元素不是自己本身
4、之前我一直疑惑一个地方：HashMap 无序且去重，一些重复的 Key 添加进去之后不就丢失了，那怎么能找到其下标呢？
通过代码可以发现，target - nums[i] 很巧妙，如果 Key 重复，也就是说 （target-nums[i]）==（target/2）。那么 nextIndx = hashtable.get(target - nums[i]); 中的 nextIndx 正是最后一次添加进来的元素的下标，而原来被替换的元素的下标就是 i，只不过被后面添加进来的给替换了

• 其他优秀代码

解法：二分思想（效率高）

public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length < 2) {
        return new int[]{};
    }
    Map<Integer, Integer> map = new HashMap<>();
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int ln0 = nums[left];
        int rn0 = nums[right];
        int ln1 = target - ln0;
        int rn1 = target - rn0;
        if (map.containsKey(ln1)) {
            return new int[]{map.get(ln1), left};
        } else {
            map.put(ln0, left++);
        }
        if (map.containsKey(rn1)) {
            return new int[]{right, map.get(rn1)};
        } else {
            map.put(rn0, right--);
        }
    }
    return new int[]{};
}

代码分析：1、
2、

题目：two-sum