题目
题目来源leetcode
leetcode地址：1. 两数之和，难度：简单。
题目描述(摘自leetcode)：
给定一个整数数组 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] 提示： 2 <= nums.length <= 104 -109 <= nums[i] <= 109 -109 <= target <= 109 只会存在一个有效答案
本地调试代码：
class Solution { public int[] twoSum(int[] nums, int target) { ... } public static void main(String[] args) { System.out.println(Arrays.toString(new Solution().twoSum(new int[]{2,7,11,15},9))); } }
题解
NO1：暴力求解（O(N2)）
思路：两层遍历循环来进行匹配两数之和。
代码：时间复杂度O(n2)
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[i] + nums[j] == target){ return new int[]{i,j}; } } } return new int[]{}; }
NO2：map构建哈希表解决
思路：利用HashMap来进行存储，key为遍历值，value为下标。每遍历一个元素值v时，直接计算target-v的值也就是待求的另一部分值，使用map来进行key索引看是否存在，一旦存在就表示匹配到了直接返回，不存在当前遍历值作为key，索引为value进行存储。
代码：O(n)
public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; if (nums == null || nums.length < 2) { return res; } Map<Integer, Integer> map = new HashMap<>(nums.length / 2 + 1); for (int i = 0; i < nums.length; i++) { //nums[i] + ? = target，这里直接使用map来进行匹配是否之前有某个数 int temp = target-nums[i]; //一旦匹配，直接赋值进行返回 if(map.containsKey(temp)){ res[0] = i; res[1] = map.get(temp); } map.put(nums[i],i); } return res; }
NO3：map+双指针(最优)
思路：其实与NO2核心思想是一致的，再此基础上使用了两个指针分别指向最左边与最右边，在使用map存储时，一次遍历相当于前后两个位置同时进行，能够大幅度提升效率。
代码：O(n)
public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map = new HashMap<>(); int left = 0; int right = nums.length-1; for(;left<=right;left++,right--){ if(map.containsKey(target-nums[left])){ return new int[]{left,map.get(target-nums[left])}; } map.put(nums[left],left); if(map.containsKey(target-nums[right]) && left!=right){ //避免中间相等的出现存储两次情况 return new int[]{right,map.get(target-nums[right])}; } map.put(nums[right],right); } return new int[2]; }
