画解算法（1.|画解算法：1. 两数之和）画解算法：1.两数之和

题目链接 https://leetcode-cn.com/problems/two-sum/
题目描述 【画解算法（1.|画解算法：1. 两数之和）】给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例：

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

解题方案思路1：两次for循环

利用两次for循环，遍历每一个元素，再将差值与其后元素一一比对，也称为“暴力法”。
时间复杂度为O(n^2)：n + (n-1) + .... + 1。

代码

class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { return new int[]{i, j}; //返回数组最简洁 } } } throw new IllegalArgumentException("No two sum solution"); //非法参数异常 } }

思路2：两遍哈希表

“暴力法”时间复杂度高，因为差值要一一和其后元素比较，如果差值一次就能和其他所有元素比较，那么时间复杂度为O(n)。
可以利用哈希表的contains()实现此功能。
因为需要返回索引，所以元素和索引要相关联，所以使用Map结构。
因为要返回索引，假设索引作为key，元素作为value，不能根据value(元素)返回其key(索引)，所以元素作为key，索引作为value。
两遍哈希表，第一遍将数据存放到map中，第二遍使用contains方法。

代码

class Solution { public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>(); //引用对象使用可指定存储类型 for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); //nums[i]做key，虽nums[i]可重复，但此时value为第二个索引，可区分；nums[i]为value，不能根据value反推key（索引）。 } for (int i = 0; i < nums.length; i++) { int key = target - nums[i]; //map.keySet().contains(key)；利用&&特性：如果map.containsKey(key)为false，map.get(key)将空指针异常；map.get(key) != i: 索引不同，确保不是同一个元素 if (map.containsKey(key) && map.get(key) != i) { return new int[]{i, map.get(key)}; } } throw new IllegalArgumentException("No two sum solution"); } }

思路3：一遍哈希表

可将第一遍哈希省略，每次循环，将元素、索引存于map，当前元素可与前面的元素比较。

代码

class Solution { public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int key = target - nums[i]; if (map.containsKey(key)) {//跟前面元素比较，肯定不是同一个元素，所以不比较索引 return new int[]{map.get(key), i}; //i在后 } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } }

画解