程序是什么,程序就是数据结构+算法+设计模式的集合,如果只是单纯的写代码,这些似乎都很遥远,可实际上,这些才是成长道路上真正要深入学习的东西,因为当项目的数据量变大,项目的业务逻辑变复杂,只有通过更好的设计才能完成想要的产品。
说说算法吧,算法的研究也是在最近才开始的,以前觉得算法挺陌生的,以为是那种十分难以理解的数学题,实际操作时,发现其实很多算法并没有想象中那么晦涩,反而很有趣,算法也包括数据库的算法,java设计的算法,以及最基本的两数之和算法,下面我就来写写我写的两数之和答案分析。
题目:给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
我的答案
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int[] numss = new int[2];
if (nums[i] + nums[j] == target) {
System.out.println(i + "," + j);
numss[0] = i;
numss[1] = j;
return numss;
}
}
}
return null;
}
刚做出来我还有点高兴,但是也发现了一些问题,使用了双层循环,实际复杂度On2 ,查询数据要做元素局的平方倍,其实是很耗性能的
看了其他人的解答,发现原来存在更好的解题方式
/**
- 解答两数之和 这是一种降低时间复杂度的方式 力扣 O(1)
*/
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");
}
使用Map时间复杂度一下子就降下来了,这里面就体现了使用Map的好处。
看来下对比,真的是如果不考虑性能,for循环可以搞定一切问题,所以说一个好的算法能抵千军万马
网友评论