题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
所以返回 [0, 1]
心得体会：拿到本题，毫无思路，看看提示，用暴力解决法实现了；但是想不到其他的优化方法，再根据提示，使用哈希表用空间换取时间，降低时间复杂度，学习到了，而且时间确实减少了不少。以下代码为证:
package priv.tzk.array; import java.util.Arrays; import java.util.HashMap; /* 题目：两数之和 题干：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 */ public class TwoSum { public static void main(String[] args) { int[] nums={3,2,4}; int target=6; // 记录程序运行时间 long start=System.nanoTime(); //获取开始时间，纳秒 System.out.println(Arrays.toString(twoSum1(nums,target))); long end=System.nanoTime(); //获取结束时间 System.out.println("程序1空间复杂度O（1）,时间复杂度O(n^2),运行时间： "+(end-start)+"纳秒"); System.out.println("-----------------------------------------------------------------------------------"); // 记录程序运行时间 long start2=System.nanoTime(); //获取开始时间，纳秒 int ret[]=twoSum2(nums,target); System.out.println(Arrays.toString(ret)); long end2=System.nanoTime(); //获取结束时间 System.out.println("程序2空间复杂度O（n）,时间复杂度O(n),运行时间： "+(end2-start2)+"纳秒"); } // 思路1：一个真正暴力的方法是搜索所有可能的数字对，但这太慢了。同样，为了完整性，最好尝试暴力解决方案。正是从这些暴力解决方案中，您可以提出优化。 // 所以，如果我们确定其中一个数字x，我们必须扫描整个数组才能找到下一个数字y=value-x,其中value是输入参数。 public static int[] twoSum1(int[] nums, int target) { int[] ret=new int[2]; for (int i=0;i<nums.length;i++) { int x = nums[i]; int y = target - x; for(int j=i+1;j<nums.length;j++) { if (nums[j] == y) { ret = new int[]{i, j}; } } } return ret; } // 思路2：在不改变数组的情况下，我们是否可以使用额外的空间？比如一个哈希表来加速搜索？ // 使用哈希表，可以将寻找 target - x 的时间复杂度从 O(N) 降低到 O(1) public static int[] twoSum2(int[] nums, int target){ int[] ret=new int[2]; HashMap<Integer, Integer> map = new HashMap<>(); for (int i=0;i<nums.length;i++) { int x = nums[i]; int y = target - x; // 使用哈希表降低搜索时间复杂度 if(map.containsKey(y)) {//查询哈希表中是否存在key为y //说明：因为是查询map表中已经存在的数据，所以map.get(y)（数组下标）的值要比i小 ret = new int[]{map.get(y),i}; break;//不停止的话，for循环一直运行下去，浪费资源 } //说明：哈希表添加数据要在查询之后，防止 例如：{1，2，3，1} target=2 输出：【0，0】 //因为根据x决定的y，所以查询y的时候，首先要排除x自身 map.put(x, i);//添加数据 x：数组num[i]的值作为key i:数组下标作为vlaue值 } return ret; } }
运行时间，对比截图：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。