您当前的位置:首页 > 计算机 > 编程开发 > Other

乘风破浪:LeetCode真题_001_TwoSum

时间:03-17来源:作者:点击数:

一、前言

沉寂了很长时间,也悟出了很多的道理,写作是一种业余的爱好,是一种自己以后学习的工具,是对自己过往的经验积累的佐证,是检验自己理解深入度的方法。在前面的模块之中,我们已经将基本的编程知识、数据结构、设计模式、应用框架、各种优化烂熟于心了,对程序开发有了一定的理解,但是编程的功力是一种水磨的功夫,需要问题,也需要思考,最重要的是需要自己用心的去打出代码,在这个过程中经验、技巧、熟练度、思考力都是非常重要的,因此我们通过LeetCode上的一些题目来锻炼一下这方面的能力。

二、LeetCode真题_001_TwoSum

2.1 题目
2.2 分析与解决

其实从问题我们就可以看出,这是类似于helloworld的一个题目,比较简单,借以引导我们从不同的角度使用不同的方法去解决问题。最简单的想法就是暴力破解方法,通过穷举所有的情况来解决问题,但是代价是时间复杂度O(n~2),空间复杂度O(1)。那么有没有其他方法呢,于是我们想到了hash表的方法,用空间换时间,通过一次遍历就能找到所有的可能结果。

通过暴力算法来解决:

 1 public int[] twoSum(int[] nums, int target) {
 2     for (int i = 0; i < nums.length; i++) {
 3         for (int j = i + 1; j < nums.length; j++) {
 4             if (nums[j] == target - nums[i]) {
 5                 return new int[] { i, j };
 6             }
 7         }
 8     }
 9     throw new IllegalArgumentException("No two sum solution");
10 }

通过hash算法来解决,又分为两次for循环和一次for循环:

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}
 1 public int[] twoSum(int[] nums, int target) {
 2     Map<Integer, Integer> map = new HashMap<>();
 3     for (int i = 0; i < nums.length; i++) {
 4         int complement = target - nums[i];
 5         if (map.containsKey(complement)) {
 6             return new int[] { map.get(complement), i };
 7         }
 8         map.put(nums[i], i);
 9     }
10     throw new IllegalArgumentException("No two sum solution");
11 }

来看看我们的算法:

 1 import java.util.Arrays;
 2 
 3 public class Solution {
 4     private static class Node implements Comparable<Node> {
 5         int val;
 6         int idx;
 7 
 8         public Node() {
 9         }
10 
11         public Node(int val, int idx) {
12             this.val = val;
13             this.idx = idx;
14         }
15 
16         @Override
17         public int compareTo(Node o) {
18             if (o == null) {
19                 return -1;
20             }
21             return this.val - o.val;
22         }
23     }
24 
25 
26     /**
27      * 题目大意
28      * 给定一个整数数组,找出其中两个数满足相加等于你指定的目标数字。
29      * 要求:这个函数twoSum必须要返回能够相加等于目标数字的两个数的索引,且index1必须要小于index2。
30      * 请注意一点,你返回的结果(包括index1和index2)都不是基于0开始的。你可以假设每一个输入肯定只有一个结果。
31      *
32      * 解题思路
33      * 创建一个辅助类数组,对辅助类进行排序,使用两个指针,开始时分别指向数组的两端,看这两个下标对应的值是否
34      * 等于目标值,如果等于就从辅助类中找出记录的下标,构造好返回结果,返回。如果大于就让右边的下标向左移,
35      * 进入下一次匹配,如果小于就让左边的下标向右移动,进入下一次匹配,直到所有的数据都处理完
36      */
37 
38     public int[] twoSum(int[] nums, int target) {
39         int[] result = {0, 0};
40 
41         Node[] tmp = new Node[nums.length];
42         for (int i = 0; i < nums.length; i++) {
43             tmp[i] = new Node(nums[i], i);
44         }
45 
46         Arrays.sort(tmp);
47 
48         int lo = 0;
49         int hi = nums.length - 1;
50 
51 
52         while (lo < hi) {
53             if (tmp[lo].val + tmp[hi].val == target) {
54 
55                 if (tmp[lo].idx > tmp[hi].idx) {
56                     result[0] = tmp[hi].idx ;
57                     result[1] = tmp[lo].idx ;
58                 } else {
59                     result[0] = tmp[lo].idx ;
60                     result[1] = tmp[hi].idx ;
61                 }
62                 break;
63             } else if (tmp[lo].val + tmp[hi].val > target) {
64                 hi--;
65             } else {
66                 lo++;
67             }
68         }
69         return result;
70     }
71 }

这种想法也比较巧妙,先对所有元素进行排序,然后通过定义首尾两个指针来不断地逼近最后的和,直至遍历完成,非常的巧妙,时间复杂度O(n),空间复杂度O(n)。不过也增加了额外的创建对象的空间。

三、总结

通过这个简单的问题,我们明白了对于一件事情,要么使用时间换取空间,要么使用空间换取时间,最后达到我们想要的结果,往往通过空间换取时间的比较多,因此hash算法就变得非常的重要了,当然也有其他的算法。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门