No.001：Two Sum

问题：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

官方难度：

Easy

翻译：

给定一个整型数组和一个给定值，返回数组中两数的下标，这两数的和为给定值，假设解集唯一确定。

例子：

给定数组{2,7,11,15}，给定值9，返回下标[0,1]。

方法一：

利用一个二次循环，在之后的数组中查找target-nums[i]是否存在。

方法一的解题代码：

     public static int[] method_1(int[] nums, int target) {

         for (int i = 0; i < nums.length - 1; i++) {

             int numberToFind = target - nums[i];

             for (int j = i + 1; j < nums.length; j++) {

                 if (nums[j] == numberToFind) {

                     return new int[] { i, j };

                 }

             }

         }

         throw new IllegalArgumentException("No two sum solution");

     }

method_1

方法二：

相对而言，在Java里面，数组是一种帮助方法相对较少的数据结构，我们可以期盼，有一种方法，可以快速的定位是否存在某一个给定的值，那么相对就可以减少内循环的时间开销。
第一个想法是List集合，List集合有List.contains()方法，迅速定位List集合中是否存在某一给定的元素，同时数组的帮助方法Arrays.asList()，可以直接将数组转化为List集合。同时，还有List.indexOf()方法，来定位下标。
想法总是美好的，但是这一方法的雷区实在太多。
数组和集合有一个很重要的差别在于，集合不能接收基本类型，你可能会想象Arrays.asList()能触发自动装箱，但是很可惜，int[]也是List集合能够接收的类型。所以你需要先显式地将int[]转化为Integer[]。
List.indexOf(target)是获取集合中第一个为target的下标，那么就无法定位例如nums[]={2,1,2}，target=4的问题。这时候自然地会想到利用List.lastIndexOf()方法。但是问题又来了，例如nums[]={3,2,4},target=6的问题，返回的数组为[0,0]，所以要优先加上index1!=idnex2的判断条件。
鉴于有这么多的雷区，就时间消耗上看，也不见得有多少提升，可能还比方法一有所不如，不推荐使用这种方法。

方法二的解题代码：

     public static int[] method_2(int[] nums, int target) {

         // 先将int[]转成Integer[]

         Integer[] collectionArray = new Integer[nums.length];

         for (int i = 0; i < nums.length; i++) {

             collectionArray[i] = nums[i];

         }

         List<Integer> list = new ArrayList<>();

         list = Arrays.asList(collectionArray);

         for (Integer a : list) {

             if (list.contains(target - a)) {

                 // 防止原数组有重复数字的情况

                 int index1 = list.indexOf(a);

                 int index2 = list.lastIndexOf(target - a);

                 if (index1 != index2) {

                     return new int[] { index1, index2 };

                 }

             }

         }

         throw new IllegalArgumentException("No two sum solution");

     }

method_2

方法三：

无论是方法一，还是方法二的算法，最大的缺点在于，它需要在剩余数组中寻找结果，当数组很大的时候，这种时间开销就相当庞大了。其实我们可以将已经遍历过的数字放入另一个数据结构中，在这个数据结构中寻找解集。

方法三的解题代码：

     public static int[] method_3(int[] nums, int target) {

         List<Integer> list = new ArrayList<>();

         list.add(nums[0]);

         for (int i = 1; i < nums.length; i++) {

             if (list.contains(target - nums[i])) {

                 return new int[] { list.indexOf(target - nums[i]), i };

             }

             list.add(nums[i]);

         }

         throw new IllegalArgumentException("No two sum solution");

     }

method_3

方法四：

仔细分析方法三中算法的时间开销，不难发现List.contains()方法在List集合中查找的效率决定了整个算法的时间开销。那么List.contains()是不是最优的查找方式呢？
说到查找速度，不可避免地想到了哈希表，自然而然的，就考虑尝试使用HashMap的数据结构，将nums[i]作为key，i作为value，同时Map集合提供Map.containsKey()方法在HashMap的实现上，拥有更高的效率。

方法四的解题代码：

 public static int[] twoSum(int[] nums, int target) {

         if (nums == null || nums.length < 2) {

             throw new IllegalArgumentException("Input error");

         }

         Map<Integer, Integer> map = new HashMap<>();

         map.put(nums[0], 0);

         for (int i = 1; i < nums.length; i++) {

             int numberToFind = target - nums[i];

             if (map.containsKey(numberToFind)) {

                 return new int[] { map.get(numberToFind), i };

             }

             map.put(nums[i], i);

         }

         throw new IllegalArgumentException("No two sum solution");

     }

twoSum

备注：

一般的算法，需要考虑入参的合理性，这一点在方法四的代码中有写出。
可以将第一个元素直接放入集合，循环从i=1开始，可以省去一次判断的操作。
虽然哈希表拥有很高的速度，但是Map的空间的开销要远比List来得多，如果效率提升不大的话，尽可能还是不要用Map了。当然，本题中对于时间效率的提升还是值得的。

巴特西

No.001：Two Sum

最新文章

热门文章