大家都说 算法 是程序员的分水岭, 三年 技术一个坎。

我工作2年已经感觉到危机感,正准备同时这面临着两个问题了,不如蹭现在还有来得及一起去把算法练起来吧,光看可不行得练。尽可能的把 https://leetcode-cn.com/ Leetcode 力扣 中的算法题都刷一遍。

遵循:先用自己的可以实现的方法做,做出来后,在看看大佬们的性能解法学习学习。 (连自己的方法都做不出来,只能偷偷的看看答案了xixixi~,不管是白猫黑猫抓到老鼠就是好猫,先要求自己做对,再最求性能)

我也会把 Leetcode 力扣 上做的题目代码,放在 GitHub 上进行同步,方便大家查阅代码,给出你的 Pr 和提出 issues

GitHub: https://github.com/aquanlerou/leetcode

两数之和(TwoSum)

首先我们先看看题目描述:

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

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/two-sum

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

我第一时间看到题目后想法,逐个逐个循环nums[]相加得出结果后,判断结果是否与 target 相等,相等后就跳出循环,这个估计是最笨的办法了。

  • 遍历数组两两相加得出结果

  • 循环中判断是否与目标数相等

    • 相等跳出循环,记录数值的位置
    • 不相等继续循环相加
  • 最后把记录的数值return返回

上代码:

public int[] twoSum(int[] nums, int target) {    
    int n = nums.length;    
    int a = 0;    
    int b = 0;    
    for(int i=0 ; i <=n; i++) {        
        for(int j=i+1; j<n; j++) {            
            int result = nums[i] + nums[j];            
            if(result == target) {                
                a = i;                
                b = j;            
            }        
        }    
    }    
    int[] resultArray = new int[]{a, b};    
    return resultArray;
}

这种解法,估计就是速度慢和性能上消耗大了。这里我还无法用什么 时间复杂度空间复杂度 去评论,因为我不懂 doge-,-,下面得好好了解下才行了。

Dalao 解法

参考:https://leetcode-cn.com/problems/two-sum/solution/jie-suan-fa-1-liang-shu-zhi-he-by-guanpengchn/

看完解法后,了解到是利用到了HashMap中的containsKey方法查找MapKey降低耗时。

  • 循环遍历

    • nums[]中的值已Key形式,和对应值的nums[]的下标已value形式存进Map
    • 循环中进行target - nums[i]计算
    • 计算结果通过containsKey方法在Map中查找是否有对应值
    • 有的话就返回map.get(target - nums[i])和循环的次数i
    • 我们最后还是得考虑下要是数组中没有对应的结果应该怎么处理,这个时候我们返回-1,-1

代码:

public int[] twoSumHash(int[] nums, int target) {    
    Map<Integer, Integer> map = new HashMap<>();    
    for (int i=0; i<nums.length; i++) {        
        int result = target - nums[i];        
        if (map.containsKey(result)) {            
        	return new int[] {map.get(result), i};        
        }        
        map.put(nums[i], i);    
    }
    return new int[] {-1, -1};
}

最后希望大家可以理解得了,可能会描述的不清楚。


I am ready to love.