乘风破浪：LeetCode真题_001_TwoSum

痛定思痛。 2021-09-30 11:46 275阅读 0赞

## 乘风破浪：LeetCode真题\_001\_TwoSum ##

### 一、前言 ###

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

### 二、LeetCode真题\_001\_TwoSum ###

#### 2.1 题目 ####

![1157683-20190102122045708-1918616567.png][]

#### 2.2 分析与解决 ####

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

**  通过暴力算法来解决：**

![1157683-20190102122557687-903385562.png][]

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循环：**

![1157683-20190102122718092-2118332187.png][]

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");
    }

![1157683-20190102122801622-386744808.png][]

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)。不过也增加了额外的创建对象的空间。**

![1157683-20190102123518222-1643907609.png][]

![1157683-20190102123555718-467276993.png][]

### 三、总结 ###

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

转载于:https://www.cnblogs.com/zyrblog/p/10207966.html

[1157683-20190102122045708-1918616567.png]: /images/20210724/bc4e65155329430e9efa73435c79d596.png
[1157683-20190102122557687-903385562.png]: /images/20210724/02c2835218ee4068af48b38c3e22d35d.png
[1157683-20190102122718092-2118332187.png]: /images/20210724/0cd58c692a7544f3ba1bdaea17cf1573.png
[1157683-20190102122801622-386744808.png]: /images/20210724/8e9ab74ef3dd4cb792eec9517c2b77d4.png
[1157683-20190102123518222-1643907609.png]: /images/20210724/6dd588a8ed304270aa9a8ecfca2af254.png
[1157683-20190102123555718-467276993.png]: /images/20210724/8c142172f11b46eb86fddf5c7abf0670.png