Two Sum II – Input array is sorted
two sum问题, 只是这次的input是sorted. 这题因为肯定有答案, 所以用二叉搜索.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public int[] twoSum(int[] numbers, int target) { for(int i = 0; i < numbers.length; i++) { int t = bs(numbers, i+1, numbers.length - 1, target - numbers[i]); if(t != -1) return new int[]{i+1, t+1}; } return null; } private int bs(int[] nums, int start, int end, int n) { while(start <= end) { int mid = start + (end - start) / 2; if(nums[mid] == n) return mid; else if(nums[mid] > n) end = mid - 1; else start = mid + 1; } return -1; } } |