给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
方法一：暴力法
遍历每一个元素，并查找是否存在一个值与target-x相等的目标元素
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 RuntimeException("No two sum solution"); } }
方法二：用hashmap空间换取时间
通过空间换去速度的方式，我们可以将查找时间从O(n)降到O(1),支持以近似恒定的时间进行快速查找近似的意思，是因为一旦发生冲突，查找时间可能会退化到O(n)，一个简单的实现使用了两次迭代，在第一次迭代中，我们将每一个元素和它的索引添加到表中，然后在第二次迭代中，我们将检查每个元素所对应的目标元素，是否存在于表中，注意该目标元素不能为本身
class Solution { public int[] twoSum(int[] nums, int target) { //定义一个新的哈希表 Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; //map.containsKey方法表示，判断Map集合对象中是否包含指定的键名 if (map.containsKey(complement)) { //先遍历数组，查找值，如果不存在相应的值，然后将对应的值，加到map里 //遍历数组 nums，i 为当前下标，每个值都判断map中是否存在 target-nums[i] 的 key 值 //判断map中是否存在，返回找到的数组下标，map.get用来获取对应值的索引 return new int[] { map.get(complement), i }; } //如果没找相应的值，就将当前的(nums[i],i)存入map map.put(nums[i], i); } //抛出异常 throw new IllegalArgumentException("No two sum solution"); } }
原文：https://www.cnblogs.com/lss0204/p/12360058.html