今天是2024.5.8,天气不好,当然也不坏。
我开始了刷题之旅。
首先开始了第一题,叫两数之和,具体需求如下:
当我看到这个题目就想到了用暴力解法?错,我想到了直接看题解,是的,我不想思考,想直接获得,我知道这是错误的,但还是这样做了。
看过题解后,暴力解法直接干,如下:
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length ;
for(int i = 0 ; i < len -1 ; i++){
for (int j = i + 1; j < len ; j++){
if(nums[j] + nums[i] == target){
return new int[]{i,j};
}
}
}
return new int[0];
}
}
这里值得注意的就是j的起始条件了,由于是从前向后遍历的,所以遍历第二个元素的时候直接从第一个元素的下一个位置开始就可以啦!所以就有了j = i + 1。为啥到 len 而不是len - 1呢,我问了GPT,GPT给出了答案:
循环条件
j < len
是为了确保j
的取值范围在有效的索引范围内。因为在第一个循环中,i
的取值范围是从 0 到len - 1
,所以j
的取值范围需要从i + 1
开始,以避免重复计算已经比较过的元素对。如果j
的取值超过了len - 1
,那么就会越界访问数组,导致错误。因此,循环条件
j < len
是为了确保j
的取值在有效范围内,遍历了数组中i
之后的所有元素。这样可以避免重复计算,并且完整地遍历了数组中的所有可能的元素对,以寻找满足条件的和为target
的元素对。总结起来,循环条件
j < len
是为了避免越界访问数组,并且确保遍历了所有可能的元素对,以找到满足条件的和为target
的元素对。
画个图就清晰多了嘿嘿。
最后记得return new int[0];不然没有返回值会报错滴。
以上暴力解法所用时间复杂度为O(),空间复杂度为O(1)。
基于以上,我又看了快速的解法,就是使用哈希表来存储,这样时间时间复杂度缩短为O(N)。当然空间复杂度就增加了,变为O(N)。
这里我理解到李叔同的 人生哪能多如意,万事只求半称心。
言归正传,开写!
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> hs = new HashMap<Integer,Integer>();
int len = nums.length;
for(int i = 0 ; i< len ; ++i){
if(hs.containsKey(target - nums[i])){
return new int [] {hs.get(target - nums[i]) , i};
}
hs.put(nums[i],i);
}
return new int [0];
}
这里面主要是创建哈希表,想象哈希表是个一块一块分布的大盒子,每次遍历元素,判断目标值减去现在在nums数组拿出来的元素的值在不在哈希表里,如果在,那么返回元素索引,不在那就放到哈希表里面。
最后,这是我第一次写博客,很开心,我知道写的不太行,这么简单的题有啥好写的。我还是写了。