力扣刷题日志-1-两数之和

2022-05-01

开始做力扣了，希望能坚持一下

频率之类的，之后再决定吧~

Day 1——两数之和

题目描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

我的想法：

由于愚钝的我不会什么高级数据结构，以一个单纯的试一试的心态想要遍历。

然而遍历失败的处理我都搞不明白了，mark变量这种已经用了这么多次的方法都记不得用，最开始的一次提交只遍历了一遍，而且没考虑负数参与的情况。

居然还过了33/57个样例

第一次的思路具体来讲是先找到比target小的一个值，如果找到了就反向遍历，直到找到差值为止

然后出现了[3,2,4] 6这个样例，这个方法想当然的被干碎了，优化处理之后添加了对单次遍历找不到的循环，但是居然还是没有改正那个小于的判断，真是纯纯煞笔

这会已经两层循环了时间复杂度已经O($n^2$)了，我还在那执迷不悟

好巧不巧卡住的样例是[0,3,4,0] 0，然后

然后我就把小于改成了小于等于

中间三个没过全是超出时间限制，全在那死循环，笑死大牙家人们

当负数出现的时候我终于意识到那个小于有多么傻逼，然后去老老实实遍历，然后就过了

除了中间有一次忘了给结果数组赋值以外

没赋值结果就是[0,x]，这都能过44/57个样例，这么多样例是第一个数作为一个元素的吗x

用时41 ms，内存消耗41.3 MB，总而言之我个人从一个寄吧的角度出发觉得还行吧

贴个代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i, j;
        int start = 0;
        boolean mark = false;
        int[] result = new int[2];
        while(mark == false) {
            for (i = start; i < nums.length; i++)
                for(j = nums.length - 1; j > i; j--)
                    if(nums[j] == target - nums[i]) {
                        result[0] = i;
                        result[1] = j;
                        mark = true;
                        break;
                    }
            start++;
        }
        return result;
    }
}

New Bee想法

看了这个想法我真的觉得我白学java

使用哈希映射方式，用java自带的Map类创建哈希表

java自带这么好用的东西居然不用

遍历一次，对数组中每个元素，都去查一次哈希表，若哈希表中不存在target与其的差值，就将其插入哈希表中

以上是图解

最后贴个New Bee代码

话说这个要不要考虑版权问题啊

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

作者：guanpengchn
链接：https://leetcode-cn.com/problems/two-sum/solution/jie-suan-fa-1-liang-shu-zhi-he-by-guanpengchn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

出处注明如上~

我怕不是这辈子都做不到这么new bee

Sum

哈希表相关（评论里提个什么哈希冲突我属实是连数据结构讲没讲过都忘了
遍历方法（你自己之前用过的东西都能忘嗷
离了IDE的自动补全怎么活

总而言之还是希望能坚持下去吧，顺便前端可能得告一段落了，因为我觉得现在的情况来看写网页不太现实了时间不够了，不过我不会放弃学前端的

以上です~