给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
package com.zcl.数组;import java.util.HashMap;/** * Author:markusZhang * VM Args: * Date:Create in 2020/2/1 14:13 */public class 两数之和 { /* 通过暴力法解决 空间复杂度O(1) 时间复杂度O(n2) */ public int[] twoSum1(int []nums,int target){ int []indexOfTwo = new int[2]; for(int i=0;i<nums.length-1;i ){ for(int j=i 1;j<nums.length;j ){ if(nums[i] nums[j]==target){ indexOfTwo[0] = i; indexOfTwo[1] = j; } } } return indexOfTwo; } /* 通过hash表解决问题 用空间换取时间 时间复杂度O(n) 空间复杂度O(n) */ public int[] twoSum2(int []nums,int target){ HashMap<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 comment = target-nums[i]; //找出map中是否有这样一个值,并且这个值不是自己。 if(map.containsKey(comment)&&map.get(comment)!=i){ return new int[]{i,map.get(comment)}; } } throw new IllegalArgumentException("没有"); } /* 进行一次hash遍历 对第二个算法的优化 */ public int []twoSum2Plus(int nums[],int target){ HashMap<Integer,Integer> map = new HashMap<>(); for(int i=0;i<nums.length;i ){ int comment = target-nums[i]; if(map.containsKey(comment)&&map.get(comment)!=i){ return new int[]{i,map.get(comment)}; } map.put(nums[i],i); } throw new IllegalArgumentException("不存在");
联系客服