LeetCode.001.Two Sum 两数之和

题目描述

001 Two Sum
https://leetcode-cn.com/problems/two-sum/
https://leetcode.com/problems/two-sum/description/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

---

相似题目

LeetCode.001.Two Sum 两数之和
LeetCode.653.Two Sum IV - Input is a BST 两数之和4-输入是BST
LeetCode.532.K-diff Pairs in an Array 数组中的k-diff数对

LeetCode.016.3Sum Closest 最接近的三数之和
LeetCode.015.3Sum 三数之和
18 四数之和
https://leetcode-cn.com/problems/4sum/

---

解题过程

非常经典的 2 Sum 问题，校招面试的时候被问过不止一次，印象最深刻的是面网易游戏时，在他们包的五道口那儿的文津酒店高层的一个房间里，二面，两个面试官，专门从杭州飞来面校招的，问的这个题。当时已经在 LeetCode 上做过了，假装思考一下就给出了答案，然后面试官问求三个数、四个数或者n个数的和等于指定值该怎么做？一下就懵逼了。

找时间把三年前校招面试的公司以及面试题整理下，我笔记里都有记录，正好现在正准备找工作，重新整理一遍也当做复习了。

现在重新做这道题，依稀记得是用哈希，思考了2分钟想出来了，思考过程是这样的：
暴力的O(n^2)搜索方法肯定会超时，因为对于每个数nums[i]我们都要去遍历整个数组看有没有nums[j]与其之和等于target，那么如何优化呢？就想到如何O(n)只遍历数组一遍，在遍历的过程中，遇到每个nums[i]都能瞬间O(1)判断有没有一个nums[j]与其之和等于target，要想瞬间判断，就只能用哈希，key是元素值，value是元素下标，从前往后遍历过程中每个元素都入库同时判断是否和之前的某个元素之和等于target。

代码如下：

private static class SolutionV2018 {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (map.get(target - nums[i]) != null) {
                result[0] = map.get(target - nums[i]);
                result[1] = i;
                break;
            }
            map.put(nums[i], i);//必须先判断再put
        }
        return result;
    }
}

需要注意的是，要先判断再put，否则遇到[3,2,3,1]，target=6这种情况会出错，第二次put(3)会把第一次覆盖。
仔细想想会知道，输入数组中如果有重复的整数，则其值肯定是target/2，否则结果就不唯一了。

---

GitHub代码

algorithms/leetcode/leetcode/_001_TwoSum.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_001_TwoSum.java

---