java 两数求和

it2022-06-22  75

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 如:给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 方法一:直接法 很容易想到两遍循环即可解决问题。

import java.sql.Array; import java.util.Arrays; import java.util.Scanner; class Solution { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String[] nums=null; nums=sc.nextLine().split(" "); int num[]=new int[nums.length]; int i=0; for(i=0;i<num.length;i++){ num[i]=Integer.valueOf(nums[i]); } //输入方法,能输入一串长度未知的数字并存入数组 int target=sc.nextInt(); System.out.println(Arrays.toString(twoSum(num,target)));//输出数组 public static int[] twoSum(int[] num, int target) { int i=0,j=0,sum=-99;//由于输入的target可能等于0,故用-99初始化 for(i=0;i<num.length;i++) { for(j=i+i;j<num.length;j++) { sum=-99; sum=num[i]+num[j]; if(sum==target)break; } if(sum==target)break; }//两次循环会消耗大量时间,尤其是在计算量大的时候。 int []index= {i,j}; return index; } } 方法二:两遍哈希表法 import java.util.Scanner; class Solution { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String[] nums=null; nums=sc.nextLine().split(" "); int num[]=new int[nums.length]; int i=0; for(i=0;i<num.length;i++){ num[i]=Integer.valueOf(nums[i]); } int target=sc.nextInt(); System.out.println(Arrays.toString(twoSum(num,target))); } class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { i, map.get(complement) }; } } throw new IllegalArgumentException("No two sum solution"); }

} 哈希表法通过使用更多的空间,能大量减少时间。


最新回复(0)