你的位置:首页 > Java教程

[Java教程]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]

思路:

1. 解唯一确定,是一个很重要的信息,将数组转为集合,利用集合的List.contains()方法,当前值a和sum-a都在集合中

解题中可能遇到的困难:

1. 数组转集合,容易出现如下错误:

1 int[] array = new int[length];2 List<Integer> list = new ArrayList<>();3 list = Arrays.asList(array);

View Code

这种情况下,编译器会报错,提示将第2行的List<Integer>转为List<int[]>。原因在于集合不会接收基本类型,而这种情况不会触发自动装箱,所以集合将int[]作为集合接收的类型。

2. 使用Arrays.asList(array)生成的集合,拥有不可使用add()和remove()一系列方法的特性,一旦使用,会抛出java.lang.UnsupportedOperationException,而且是运行时异常,编译器不会报错。

解题代码:

 1 private static int[] method(int[] array, int sum) { 2     // 结果数组 3     int[] result = new int[2]; 4     // 保护无结果的标志位 5     boolean flag = false; 6     // 先将int[]转成Integer[] 7     Integer[] collectionArray = new Integer[array.length]; 8     for (int i = 0; i < array.length; i++) { 9       collectionArray[i] = array[i];10     }11     List<Integer> list = new ArrayList<>();12     list = Arrays.asList(collectionArray);13     list.remove(0);14     for (Integer a : list) {15       if (list.contains(sum - a)) {16         result[0] = list.indexOf(a);17         result[1] = list.lastIndexOf(sum - a);18         flag = true;19         break;20       }21     }22     if (flag) {23       return result;24     }25     return null;26   }

View Code

测试代码地址:

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/easy/Q001.java

LeetCode题目地址:

https://leetcode.com/problems/two-sum/

PS:如有不正确或提高效率的方法,欢迎留言,谢谢!