大家都说 算法 是程序员的分水岭， 三年 技术一个坎。 我工作2年已经感觉到危机感，正准备同时这面临着两个问题了，不如蹭现在还有来得及一起去把算法练起来吧，光看可不行得练。尽可能的把 https:/// Leetcode 力扣 中的算法题都刷一遍。 遵循：先用自己的可以实现的方法做，做出来后，在看看大佬们的性能解法学习学习。 （连自己的方法都做不出来，只能偷偷的看看答案了xixixi~，不管是白猫黑猫抓到老鼠就是好猫，先要求自己做对，再最求性能） 我也会把 Leetcode 力扣 上做的题目代码，放在 GitHub 上进行同步，方便大家查阅代码，给出你的 Pr 和提出 issues 。 GitHub: https://github.com/aquanlerou... 两数之和（TwoSum）首先我们先看看题目描述： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]
来源：力扣（LeetCode） 链接：https:///probl... 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我第一时间看到题目后想法，逐个逐个循环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:///probl... 看完解法后，了解到是利用到了HashMap中的containsKey方法查找Map中Key降低耗时。 循环遍历 把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};
}
最后希望大家可以理解得了，可能会描述的不清楚。
|
