力扣刷题笔记——01.两数之和

张开发
• 2026/4/16 8:46:11 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

力扣刷题笔记——01.两数之和
题目链接​​​​​​1. 两数之和 - 力扣LeetCode​​​​​思路一暴力枚举核心逻辑在数组里固定一个数在剩下的数中找另一个数使二者相加等于target;代码实现1class Solution { 2 public int[] twoSum(int[] nums, int target) { 3 //根据给定的目标数值循环在数组里找 然后返回数组下标 4 int nnums.length; 5 for(int i0;in;i){ 6 for(int ji1;jn;j){//固定一个数后从固定数的下一个开始找 所以ji1,同时保证下标不重复 7 if(nums[i]nums[j]target){ 8 return new int[]{i,j}; 9 } 10 } 11 } 12 return new int[]{}; 13 } 14}时间复杂度O(n2)两个循环嵌套空间复杂度O(1),仅使用了常数个额外变量不随输入规模变化。2.思路二哈希表核心逻辑用 HashMap 的 O(1) 查找特性将“搜索另一半”的过程从 O(n) 降维到 O(1)。创建空哈希表 然后循环 找另一半数的时候如果找到的话返回两个数再数组中的位置没找到的话先把已知的数存入map,继续循环 直到找到另一半数 返回。代码实现class Solution { public int[] twoSum(int[] nums, int target) { MapInteger,Integer mapnew HashMap(); int nnums.length; for(int i0;in;i){//从第一个开始找 int xtarget-nums[i]; //算出要找的另一个数 if(map.containsKey(x)){//查找map里是否含有该数 return new int[]{map.get(x),i};//若有获取该数位置并一起返回 } map.put(nums[i],i);//没有查找到的话就把已知数存入map } return new int[]{}; } } //26.4.6再做 本来想key下标value元素内容.dp一下本题是根据数值去查找是否存在过查的时候使用数值而不是下标 //所以要查什么,什么就是key。在这题里数值-key,找到之后我需要知道他的下标-value //for(int i0;inums.length;i){ // int currentnums[i]; // int needtarget-current; // if(map.containsKey(need)){ // return new int[]{map.get(need),i}; // } // map.put(current,i); // } // return new int[0];时间复杂度O(n)n 是数组中的元素数量。我们只需遍历一次数组每次在哈希表中查找目标元素的时间复杂度均为 O(1)。空间复杂度O(n)。主要取决于哈希表的开销最坏情况下我们需要将数组中所有 n个元素都存入哈希表。3.避坑与反思循环边界最初写暴力法时容易混淆 i 和j的起始位置必须保证j i 1才能避免“自己加自己”以及重复计数。存储逻辑在哈希法中map.put应该放在containsKey判断之后。因为我们要找的是“过去出现的数”如果先把当前数存进去再找可能会导致在target 6, nums[i] 3的情况下自己匹配到了自己。

更多文章