Question:
My code:
public class Solution {
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0)
return null;
int[] result = new int[2];
boolean isOver = false;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i + 1;
result[1] = j + 1;
isOver = true;
break;
}
}
if (isOver)
break;
}
return result;
}
}
My test result:
这道题目终于是花了几分钟写出来的。但是复杂度的确是 quadratic的。
后来看了别人的解题思路，觉得的确别人的更加快，只要 o(n).
他的做法就是设置一个hashmap, 存放键值对。
key -> 要得到target所需要的另外一个加数。
value -> 该加数所对应的index
然后对数组进行遍历。每碰到一个新的加数时，查找哈希表，看看其是否已经存在于该表中，即，其是否已被其他数所需要。如果已经存在了，说明有个数可以和他加起来达到目的。然后将它们返回。如果不存在，则将 target - 该加数 的值存入哈希表中，对应的value是 其 index (i + 1).
这就是这道题目的思路。
这是那人的代码：
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>();
int len = nums.length;
for(int i = 0; i < len; i++){
if(tracker.containsKey(nums[i])){
int left = tracker.get(nums[i]);
return new int[]{left+1, i+1};
}else{
tracker.put(target - nums[i], i);
}
}
return new int[2];
}
**
总结：有个疑问， HashMap 和 HashSet到底有什么区别呢？
解答： HashMap -> 添加元素时，添加的 key-value
HashSet -> 添加元素时，添加的value 他的key默认为 数组的index。算是更加简化的HashMap
**
Anyway, Good luck, Richardo!
import java.util.Arrays;
import java.util.HashMap;
public class Solution {
/* Solution 1. O(n^2)
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0)
return null;
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++)
hm.put(nums[i], i);
int[] constant = Arrays.copyOf(nums, nums.length);
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int sum = nums[i] + nums[j];
if (sum == target) {
int index1 = hm.get(nums[i]) + 1;
int index2 = hm.get(nums[j]) + 1;
if (index1 == index2) // if nums[i] = nums[j] and i != j
index2 = findIndex(constant, nums[i], index1) + 1;
if (index2 > index1)
return new int[] {index1, index2};
else
return new int[] {index2, index1};
}
else if (sum > target)
break;
}
}
assert false; // program should not come here according to the assumption of question
return null;
}
private int findIndex(int[] nums, int target, int origin) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target && i != origin)
return i;
}
return -1;
}
*/
/** Solution2 : O(n) */
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0)
return null;
HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (tracker.containsKey(nums[i])) {
int left = tracker.get(nums[i]);
return new int[] {left + 1, i + 1};
}
else {
tracker.put(target - nums[i], i);
}
}
assert false;
return null;
}
}
上面的是我的解法。比最早的做法好处在于，我一开始排了个序，所以当nums[i] + nums[j] > target时我就可以停止搜索了。但同样的，排序之后index也乱了，所以我采用了HashMap来解决这个问题。
然后又引入了一个新的问题。nums数组里面会有value重复。那么index就会被覆盖。所以当我发现value重复时，我需要到原数组中找到另外一个同value不同key的index。
所以我还需要将原数组拷贝一份后再排序，打乱index。
这么做复杂度虽然仍是O(n^2),但系数会小很多。
然后我使用到了Arrays.copyOf(...)
以前我一直在想，怎么给数组排序后还能准确找到他的原index。这道题木我的做法不失为一种好的解决方法。先拷贝一份原数组。然后将原数组插入到HashMap中。之后再排序。然后相应的操作再从HashMap中取出index。如果出现重复value的现象，再利用拷贝数组进行相应的操作。
虽然显得有些麻烦。
然后注意一个小细节。
我在最后返回null之前，有这么一句，
assert false;
这样的化当我允许使用assert时，如果程序跑到这里就一定会报错的。
因为我的假设是，程序不可能跑到这里。
这么一种做法可以广泛应用于代码中，使debug更加简单。
还学习到了一个命名，
tracker, good name
然后我看到了这个O(n)的解法，的确很巧妙。
赞一个。
Anyway, Good luck, Richardo!
