// 小白一名，0算法基础，艰难尝试算法题中，若您发现本文中错误，
或有其他见解，往不吝赐教，感激不尽，拜谢。
领扣 第2题 今日算法
题干
//给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
//
// 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
//
// 示例:
//
// 给定 nums = [2, 7, 11, 15], target = 9
//
// 因为 nums[0] + nums[1] = 2 + 7 = 9
// 所以返回 [0, 1]
初次尝试
/*
* 第一思路，仍是暴力解题
* 每个元素与除自身外的元素相加
* 何时与目标值相等，何时打破循环
* 不出意外 只超过了 17.2%的玩家
* 一组数据时间约为25ms
* */
public int[] twoSum1(int[] nums, int target) {
int first;
int second;
int a;
int b=1;
//外循环 假设第一个值为索引为a
out:
for (a = 0; a < nums.length; a++) {
first=nums[a];
//内循环 假设第二个值索引为b
for(b=a+1;b<nums.length;b++){
second=nums[b];
//判断时候相等 相等跳出所有循环
if(first+second==target){
break out;
}
}
}
//返回值
return new int[]{a,b};
}
初次尝试
/*
* 想了下 之前的代码约为n方次
* 一组数据两两组合且不重复为为n*（n-1）/2
* 按照获得此公式的逻辑
* 改动下了代码 因为代码本身很简单 便没有写注释
* 其实是头疼，太累了
* 本次用时约为 12ms 快了一倍
* */
public int[] twoSum2(int[] nums, int target) {
int first;
int second;
for(int a=1;a<nums.length;a++){
first= nums[a];
second=target-first;
for(int b=0;b<a;b++){
if(second==nums[b]){
return new int[]{a,b};
}
}
}
return null;
}
第二次尝试
/*
* 下面是 目前的最优代码之一
* 因为我认为这个网站的数据量并不够大
* 可能会存在误差
* 思路跟我的一样，但是使用了HashMap
* 使用是否包含代替了我的一次循环
* 不太明白为什么会比我快了这么多
* 应该是因为 HashMap的底层查找要优于循环吧
* 明天再看看吧
* */
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>(nums.length);
for(int i = 0; i < nums.length; i++){
if(map.containsKey(target - nums[i])){
return new int[]{i, map.get(target - nums[i])};
} else {
map.put(nums[i], i);
}
}
return null;
}
第三次尝试
今天学servlet用到了druid 才发现之前的连接池这块已经忘了好多
想要复习，可又想去学习概率论和算法
心情复杂 取舍难定
年轻时我觉得钱是最重要的，到老发现，的确如此。
When I was young，I used to think that money was the most important thing in life,now I am old,I know it is.
写于 2018.11.18