🍔题目
题目链接:两数之和
给一个整数数组nums和一个整数目标值target,请在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。
每种输入只会对应一个答案,但是数组中同一个元素在答案里不能同时出现,可以按照任意顺序返回答案。
示例:
🌭题目解析
🍟解题思路及代码展示
🥫思路1
暴力解决,题目要求两数之和,所以每个数对应一个循环,也就是两个循环嵌套,当满足这两个数的和等于目标值时,保存这两个数的下标然后返回
👁️🗨️代码展示:
class Solution { public int[] twoSum(int[] nums, int target) { int[] ret = new int[2]; for(int i = 0;i < nums.length;i++){ for(int j = i+1;j < nums.length;j++){ if(nums[i]+nums[j] == target){ ret[0] = i; ret[1] = j; return ret; //找到值后直接返回,避免后续循环 } } } return ret; } }
时间复杂度:两层循环嵌套,故时间复杂度为O(n^2)
🥫思路2
我们可以借助HashMap这一数据结构,遍历数组,判断HashMap中的key是否存有target-nums[i],如果存在,第一个数的下标为hashmap.get(target-nums[i]),第二个数的下标为i,如果不存在,将nums[i]-i作为K-V键值对存入HashMap中,依次循环直到判断存在
🤔解释说明:
👁️🗨️代码展示:
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> m = new HashMap<>(); int[] ret = new int[2]; for(int i = 0;i < nums.length;i++){ if(m.containsKey(target-nums[i])){ ret[0] = m.get(target-nums[i]); ret[1] = i; } m.put(nums[i],i); //存入值-下标 } return ret; } }
时间复杂度:只有一个循环,故时间复杂度为O(n)