网站制作公司价格,大网站建设公司,织梦安防网站源码,洛阳市建设规划局网站题目#xff1a;
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一个元素在答案里不能重复出现。
你…题目
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。
示例 2
输入nums [3,2,4], target 6
输出[1,2]示例 3
输入nums [3,3], target 6
输出[0,1]
提示
2 nums.length 104-109 nums[i] 109-109 target 109只会存在一个有效答案 解决
解法1暴力求解
看数组中一个数与数组中其它数的和是不是等于目标值是就返回结果不是就继续循环。时间复杂度为O(n^2)。
public int[] twosum(int[] nums,int target) {int[] resultnew int[2];for(int i0;inums.length;i){for(int ji1;jnums.length;j){if(nums[i]nums[j]target) {result[0]i;result[1]j;return result;}}}return result;
} 解法2用HashMap存储每个数对应的下标
改进减少重复扫描。引用hashmap。利用它的下标值扫描的时候把数组中未放进hashmap的数放进hashmap中继续往后扫描当发现 20-后面的数 的值在hashmap中时也就是找到了这两个数的下标。时间复杂度为O(n)。
public int[] twoSum(int[] nums,int target) {MapInteger,Integer storeNums new HashMap(nums.length,1);int[] resultnew int[2];for(int i0;i nums.length;i) {int anothertarget-nums[i];Integer anotherIndexstoreNums.get(another);if(null!anotherIndex) {result[0]anotherIndex;result[1]i;break;}else {storeNums.put(nums[i],i);}}return result;} 解法3与解法2类似存储每个数对应下标
时间复杂度为O(n)。
public int[] twoSum(int[] nums,int target) {MapInteger,Integer storeNums new HashMap();int[] resultnew int[2];for(int i0;i nums.length;i) {int anothertarget-nums[i];if(storeNums.containsKey(nums[i])) {int anotherIndexstoreNums.get(nums[i]);result[0]anotherIndex;result[1]i;break;}else {storeNums.put(target-nums[i],i);}}return result;} 加油加油^_^
