给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
class Solution { public int[] twoSum(int[] nums, int target) { int[] arr = new int[2]; for(int i = 0;i < nums.length;i++){ for(int j = i+1;j < nums.length;j++){ if(i != j && nums[i]+nums[j] == target){ arr[0] = i; arr[1] = j; break; } } } return arr; } }
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[i]+nums[j] == target){ int[] arr = new int[] {i,j}; return arr; } } } throw new IllegalArgumentException("No two sum solution"); } }
时间复杂度O(n2)，空间复杂度O(1);
class Solution { public int[] twoSum(int[] nums, int target) { //利用哈希表进行两遍迭代 Map<Integer,Integer> map = new HashMap<>(); //第一遍迭代把数组元素都放到x哈希表中 for(int i = 0;i < nums.length;i++){ map.put(nums[i],i); } //第二遍是找哈希表中的元素值是否等于（target - nums[i]）; for(int i = 0;i < nums.length;i++){ int jkey = target - nums[i]; if(map.containsKey(jkey) && map.get(jkey) != i){ return new int[] {i,map.get(jkey)}; } } throw new IllegalArgumentException("No two sum solution"); } }
时间复杂度O(n)，空间复杂度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]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } }
时间复杂度O(n)，空间复杂度O(n);
原文：https://www.cnblogs.com/fsgNL/p/12815478.html