Two Sum

从今天起的LeetCode

---

这些天发现自己的算法是真的不行，那直接刷leetcode好了找了好些个leetcode项目以便于参考、对比、学习

参考与致谢

• 算法珠玑java版PDF：https://github.com/soulmachine/leetcode

• 算法珠玑：https://github.com/soulmachine/algorithm-essentials

• 有题号(解答写在了issue，解析详尽)：https://github.com/grandyang/leetcode

• 有题号、分类并制作了PDF，无解析：https://github.com/dingjikerbo/Leetcode-Java

• 有分类：https://github.com/yuanguangxin/LeetCode

• 有题号、分类：https://github.com/Blankj/awesome-java-leetcode

• 有题号、题量大(1000+)：https://github.com/fishercoder1534/Leetcode

• leetcode中文官网：https://leetcode-cn.com/problemset/all/

001 Two Sum

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

分析

LeetCode的第一题最简单的做法是两重for循环去遍历，时间复杂度是为O(n^2)，这样会TLE(Time Limit Exceeded)
更佳的做法是，直接遍历查找target-nums[i]。在遍历数组的时候，用 target 减去遍历到的数字，就是另一个需要的数字了，直接在 HashMap 中查找其是否存在即可。先把数组存进map，key为数值，value为下标要注意map.put要放在for末尾，对于case[3, 3], target=6的情况，如果放在开头会覆盖第一个3

参考：dingjikerbo、grandyang

题解

执行用时：2 ms, 在所有 Java 提交中击败了99.65%的用户内存消耗：40.2 MB, 在所有 Java 提交中击败了15.27%的用户

public int[] twoSum(int[] nums,int target){
    HashMap<Integer,Integer> map = new HashMap<>();
    for (int i = 0;i < nums.length;i++){
        if (map.containsKey(target-nums[i])){
            return new int[]{map.get(target-nums[i]),i};
        }
        map.put(nums[i], i);//第一轮循环先把数组写进map，节省了一个for循环
    }
    return null;
}

笔记

Map.containsKey：如果此映射包含指定键的映射关系，则返回 true。
Map.containsValue：如果此映射将一个或多个键映射到指定值，则返回 true。

题目来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/two-sum