经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
【算法】LeetCode算法题-Two Sum
来源:cnblogs  作者:小川94  时间:2018/10/16 9:17:25  对本文有异议

程序 = 数据结构 + 算法。

算法是每一位程序员学习成长之路上无法避开的重要一环,并且越早接触越好。今后会每天做些算法题,至少每天做一道题目,同时会记录自己的解题思路和代码,通过【算法】专题来分享。针对数据结构这一块的知识,我也会抽时间补习,毕竟不是科班出生,从长远看,数据结构与算法学的越早越扎实越好,不管你使用的是哪一种开发语言。

01 看题和准备

给定一个整数数组和一个目标整数,该目标整数满足数组中两元素之和,返回数组中两个数字的下标索引,以数组形式表示结果。例如给定数组int[] nums = [2, 7, 11, 15],目标整数int target = 9,因为 nums[0] + nums[1] = 2 + 7 = 9,返回包含两数索引的数组[0, 1]。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 分析题目

这道题目求的是数组内任意两元素之和等于给定的目标整数,于是很容易想到数组for循环遍历,并且是两层for循环,于是第一版的代码思路已经有了。

  1. public int[] twoSum(int[] nums, int target) {
  2. int[] result = new int[2];
  3. if (nums.length < 2) {
  4. return null;
  5. }
  6. try {
  7. for (int i=0; i<nums.length; i++) {
  8. for (int j=i+1; j<nums.length; j++) {
  9. if (nums[i] + nums[j] == target) {
  10. result[0] = i;
  11. result[1] = j;
  12. }
  13. }
  14. }
  15. } catch (Exception e) {
  16. e.printStackTrace();
  17. return null;
  18. }
  19. return result;
  20. }

03 是否还可以优化?

上面的解法是两层循环,循环次数是n*(n-1)次,n为数组元素个数,n越大,程序执行的时间越长,那能不能只循环一次?既然可以做加法匹配,那做减法呢?先拿到目标整数与数组中每位元素的差值,再去判断此差值是否存在于此数组中。这时,我们需要一个存新数据的集合,既包含每位元素,也包含每位元素的索引,对此选取Map作为存放新数据的对象。

  1. public int[] twoSum2(int[] nums, int target) {
  2. int[] result = new int[2];
  3. if (nums.length < 2) {
  4. return null;
  5. }
  6. try {
  7. Map<Integer, Integer> map = new HashMap<>();
  8. for (int k=0; k<nums.length; k++) {
  9. int num = target - nums[k];
  10. if (map.containsKey(num)) {
  11. result[0] = map.get(num);
  12. result[1] = k;
  13. }
  14. map.put(nums[k], k);
  15. }
  16. } catch (Exception e) {
  17. e.printStackTrace();
  18. return null;
  19. }
  20. return result;
  21. }

第二版的解法只用了一层循环,对比第一版解法,从时间花费上看,第二版的解法是优于第一版的。

04 小结

本篇只是作为一个开题,后续会将其他算法题按照上面的格式分享给大家,如果有什么好的解法、建议或者其他问题,可以下方留言交流!

本文首发于我的个人公众号:悦乐书,转载请注明出处!

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号