Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
OJ:
- 首先用最笨的方法来解，不过好像Java Array的相关method我都忘得差不多了....记录下来再更正吧
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public class Solution { public int[] twoSum(int[] numbers, int target) { int[] result = new int[2]; int l = numbers.size(); int i, j; for (i = 0; i < l; i++){ for(int j = i + 1; j < l; j++){ if(numbers[i] + numbers[j] = target){ result[0] = i; result[1] = j; return result; } } } } } |
- Result: Line4: error: cannot find symbol: method size()
忘记有没有直接看Array长度的函数了，先不去查文档，转化成熟悉的String来做
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
public class Solution { public int[] twoSum(int[] numbers, int target) { String source = numbers.toString(); int[] result = new int[2]; //int l = numbers.size(); l = source.length(); int i, j; for (i = 0; i < l; i++){ for(int j = i + 1; j < l; j++){ if(numbers[i] + numbers[j] = target){ result[0] = i; result[1] = j; return result; } } } } }
Result: Line 6: error: cannot find symbol: variable l 这个错误就是粗心大意了, 后面还有一个错误: Line 9: error: variable j is already defined in method twoSum(int[],int) 我还是再看一遍code再提交吧
审查了一遍,又发现个错误, i的边界判定不应该是length, 而应该是length - 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
public class Solution { public int[] twoSum(int[] numbers, int target) { String source = numbers.toString(); int[] result = new int[2]; int l = source.length(); int i, j; for (i = 0; i < l - 1; i++){ for(j = i + 1; j < l; j++){ if(numbers[i] + numbers[j] = target){ result[0] = i; result[1] = j; return result; } } } } }
Result: Line 9: error: unexpected type
太不严谨了 - -, 平常用eclipse确实有依赖性, 函数名自己都不去记了, 这种 "==" 自己居然也没注意到
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
public class Solution { public int[] twoSum(int[] numbers, int target) { String source = numbers.toString(); int[] result = new int[2]; int l = source.length(); int i, j; for (i = 0; i < l - 1; i++){ for(j = i + 1; j < l; j++){ if(numbers[i] + numbers[j] == target){ result[0] = i; result[1] = j; return result; } } } } }
Result: Line 17: error: missing return statement
简直是错误百出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
public class Solution { public int[] twoSum(int[] numbers, int target) { String source = numbers.toString(); int[] result = new int[2]; int l = source.length(); int i, j; for (i = 0; i < l - 1; i++){ for(j = i + 1; j < l; j++){ if(numbers[i] + numbers[j] == target){ result[0] = i; result[1] = j; return result; } } } return result; } }
Result: Runtime Error Message: Line 9: java.lang.ArrayIndexOutOfBoundsException: 3 Last executed input: [3,2,4], 6
再改!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
public class Solution { public int[] twoSum(int[] numbers, int target) { String source = numbers.toString(); int[] result = new int[2]; int l = source.length(); int i, j; for (i = 0; i <= l - 2; i++){ for(j = i + 1; j <= l - 1; j++){ if(numbers[i] + numbers[j] == target){ result[0] = i + 1; result[1] = j + 1; return result; } } } return result; } }
Result: Runtime Error Message: Line 9: java.lang.ArrayIndexOutOfBoundsException: 3 Last executed input: [3,2,4], 6
IMPORTANT: 之所以会这样, 是因为Arrays.toString(), 并不是返回的Arrays里面元素的值, 比如 int[] numbers = {3, 2, 4}, 实测 System.out.println(numbers.toString()) 结果为 [I@53281264 所以上面code中的length实际为11, 怪不得会出现ArrayIndexOutOfBoundsException.
正确获得Arrays长度的方法: Arrays.length
之前刷提的时候不知所以然, 这次我们进阶了, 其实刚才写代码的时候也想到直接用 Arrays.length, 但是这个 .length不是一个method呀, 这在一切皆是Object的Java中显得有些不合群, 所以没用, 这次问题的出现是必然的, 因为我没有系统的学习过数据结构也好, 算法也好, Java也好, 以点带面, 查缺补漏吧.
还是参考StackOverflow的解释: 为什么ArrayList可以用ArrayList.size()来获取ArrayList的长度, 而 Array.length -- 并不是一个method, 却可以得到Array的长度呢?
Arrays are special objects in java, they have a simple attribute named length which is final. There is no "class definition" of an array (you can't find it in any .class file), they're a part of the language itself.
The members of an array type are all of the following: The public final field length, which contains the number of components of the array. length may be positive or zero. The public method clone, which overrides the method of the same name in class Object and throws no checked exceptions. The return type of the clone method of an array type T[] is T[]. A clone of a multidimensional array is shallow, which is to say that it creates only a single new array. Subarrays are shared. All the members inherited from class Object; the only method of Object that is not inherited is its clone method. Note also that ArrayList.size() provides the number of object actually stored in the array whereas myArray.length ([]) provides the "capacity". That is, if for myArray = new int[10];, it returns 10. It is not the number of objects you've put in the array.
改正Arrays.length :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
public class Solution { public int[] twoSum(int[] numbers, int target) { String source = numbers.toString(); int[] result = new int[2]; // int l = source.length(); int l = numbers.length; int i, j; for (i = 0; i <= l - 2; i++){ for(j = i + 1; j <= l - 1; j++){ if(numbers[i] + numbers[j] == target){ result[0] = i + 1; result[1] = j + 1; return result; } } } return result; } }
改正这一错误之后的代码可以正确运行了, 但是 leetcode的OJ表示此程序太慢了, Time Limit Exceeded.
这并不出乎意料, 因为这个是最笨的方法, 时间复杂度应该是O(n^2)