免费发布信息网站,凉山建设网站,做电影网站需要什么条件,wordpress 导入用户为找工作#xff0c;我的代码都是用的JAVA#xff0c;慢慢学习中。
LeetCode刷题Day1
两数之和
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。
你可以假设每种输入…为找工作我的代码都是用的JAVA慢慢学习中。
LeetCode刷题Day1
两数之和
给定一个整数数组 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只会存在一个有效答案
**进阶**你可以想出一个时间复杂度小于 O(n2) 的算法吗
解题方法
1.暴力求解
枚举在数组中所有的不同的两个下标的组合逐个检查它们所对应的数的和是否等于target
复杂度分析 时间复杂度: O ( n 2 ) O(n^2) O(n2)这里n为数组的长度。
空间复杂度: O ( 1 ) O(1) O(1)只用到常数个临时变量。
class Solution {public int[] twoSum(int[] nums, int target) {int len nums.length;for(int i0;ilen-1;i){for(int ji1;jlen;j){if(nums[i]nums[j]target){return new int[]{i,j};}}}throw new IllegalArgumentException(No two sum solution);//不写不能通过}public static void main(String[ ] args){int[] arrayName {2,7,11,15};Solution s new Solution();int[] indexss.twoSum(arrayName,9);for (int i 0; i indexs.length; i) {System.out.print(indexs[i] );}}
}我自己想到的也是这个暴力破解因为其他不熟练但是第一个for循环我原本写的是(ilen)听了官方视频讲解说是每种输入只会对应一个答案所以和内循环区分一下。 这里要说下java中数组的定义
new int[]{1,2,3}int[] nums new int[5]; nums[0]1;int[] nums Array.create(1, 2, 3, 4, 5);//使用Array类的静态方法创建和初始化数组:int[] source {1, 2, 3, 4, 5};//使用Arrays类的静态方法复制、排序等操作数组: int[] target Arrays.copyOf(source, source.length); // 复制数组 Arrays.sort(target); // 对目标数组进行排序
对于代码中抛出的异常要加上这句是因为如果数组nums中不存在符合条件的两个数就不会有返回值而函数定义的时候定义的返回类型是int[]会报错所以需要抛出异常。 再看看这个异常IllegalArgumentException是非法参数异常当传递给方法的参数不满足预期时比如传入了无效的参数或空值容易引发此异常如果找不到符合条件的两个数就抛出这个非法参数异常错误信息是“No two sum solution”。
2.查找表法 在遍历的同时记录一些信息以省去一层循环这是“以空间换时间的想法 需要记录已经遍历过的数值和它所对应的下标可以借助查找表实现 查找表有两个常用的实现: 哈希表 平衡二叉搜索树
复杂度分析
时间复杂度:O(n)这里n为数组的长度。空间复杂度:O(n)哈希表里最多需要存n-1个键值对。
class Solution1 {public int[] twoSum(int[] nums, int target){int len nums.length;MapInteger,Integer hashMap new HashMap(len-1);hashMap.put(nums[0], 0);//这一行也可以不加因为下面的for循环也会加入的for (int i 0; i len; i) {int another target-nums[i];if (hashMap.containsKey(another)){return new int[]{i,hashMap.get(another)};}hashMap.put(nums[i],i);}throw new IllegalArgumentException(No two sum solution);}
}图片和代码来自leetcode官网
思路定义一个Map存放键值对默认将nums[0]添加进去Map这里用put添加元素官方给出的代码这边初始化了一下但在for循环中nums[0]又被加了一下。 public static void main(String[] args) {MapInteger,Integer hashMap new HashMap(5);hashMap.put(0,1);hashMap.put(0,1);for (Map.EntryInteger, Integer entry : hashMap.entrySet()) {System.out.println(Key: entry.getKey() , Value: entry.getValue());}//Key: 0, Value: 1}我不太了解这个结构就敲代码试了一下同样的值加两次Map他实际第2次会覆盖第1次应当是按键来存值的一个键只能一个值。 这里给hashMap赋初值大概是出于一个程序员的谨慎就和写文件动不动就ctrlS一样hhh。
接着开始遍历对于nums[0]也就是6他需要找到一个值为2的当前Map中没有2没有就将他存入Map中对于nums[1]也就是3他需要找到一个值为5的当前Map中没有5,没有就将他存入Map中;对于nums[2]也就是8他需要找到一个值为0的当前Map中没有0,没有就将他存入Map中;对于nums[3]也就是2他需要找到一个值为6的当前Map中有6,找到了因为题目中说每种输入只会对应一个答案找到了就返回new int[]{i,hashMap.get(another)}。
再思考一下为什么要将数组的下标和值将值变为map中的键下标变为map中的值大概是因为这样好操作可以根据值得到我们要的下标。脑子不够用需要理一下思路。
如有错误请指正
