Screenshot from 2016-03-01 21:28:37.png
My code:
public class Solution {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length < 2)
return null;
HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
if (tracker.containsKey(numbers[i])) {
int[] ret = new int[2];
ret[0] = tracker.get(numbers[i]) + 1;
ret[1] = i + 1;
return ret;
}
else {
tracker.put(target - numbers[i], i);
}
}
return null;
}
}
不知道这道题目有什么意义。跟2sum不是差不多嘛？
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == 0) {
return null;
}
int begin = 0;
int end = numbers.length - 1;
while (begin < end) {
int sum = numbers[begin] + numbers[end];
if (sum > target) {
end--;
}
else if (sum < target) {
begin++;
}
else {
int[] ret = new int[2];
ret[0] = begin + 1;
ret[1] = end + 1;
return ret;
}
}
return null;
}
}
reference:
https://leetcode.com/articles/two-sum-ii-input-array-sorted/
看到这道题目，我首先想到了两个解法。
第一个就是用hashtable
time: O(n)
space: O(n)
第二种是用 遍历 + binary search
time: O(n logn)
space: O(1)
有没有种算法，
time: O(n)
space: O(1)
当然是有的。这种排好序的数列，就是天生为了双指针而存在的。
Anyway, Good luck, Richardo! -- 09/02/2016
