001-两数之和

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/two-sum/

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

二、思路

维护一个 map，将当前值和下标都存里面，然后用 count 去判断两个之和是不是目标值。

三、代码

3.1 C++

class Solution {
   public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i, j;
        vector<int> results;
        map<int, int> hmap;
        for (i = 0; i < nums.size(); i++) {
            // 检查 hmap中是否有 num[i] 没有的话将 num[i]
            if (!hmap.count(nums[i])) {
                hmap.insert(pair<int, int>(nums[i], i));
            }
            // 如果 target - nums[i] 也在 hmap 中
            if (hmap.count(target -nums[i]))
            {
                // 获得这个数的索引
                int n = hmap[target - nums[i]];
                if (n != i) {
                    results.push_back(n);
                    results.push_back(i);
                    return results;
                }
            }
        }
        return results;
    }
};

3.2 Java

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 边存边找
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            // map 里面没有这个值
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            }
            // 放进去后直接再判断
            if (map.containsKey(nums[i])) {
                // map 里面有这个 target - nums[i]，说明找到了，但是还要判断不是当前值
                if (map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i) {
                    res[0] = i;
                    res[1] = map.get(target - nums[i]);
                    return res;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {2, 9, 11, 15};
        int target = 11;
        Solution a = new Solution();
        a.twoSum(nums, target);
    }
}

3.3 JavaScript

/**
 * 两数之和
 *
 * @param {number[]} nums 整数数组
 * @param {number} target 目标值
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let map = new Map();
  let res = new Array();
  for (let i = 0; i < nums.length; i++) {
    if (!map.has(nums[i])) {
      map.set(nums[i], i);
    }

    if (map.has(target - nums[i]) && map.get(target - nums[i]) != i) {
      res.push(i);
      res.push(map.get(target - nums[i]));
      return res;
    }
  }
  return res;
};