167. Two Sum II - Input array is sorted

167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, 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 and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

public class Solution { public int[] twoSum(int[] numbers, int target) { if(numbers==null || numbers.length < 1) return null; int i=0, j=numbers.length-1; while(itarget) { --j; } else { return new int[]{i+1, j+1}; } } return null; } }

public class Solution { public int[] twoSum(int[] numbers, int target) { int low = 0; int high = numbers.length - 1; if (numbers[low] >= 0 && target < numbers[high]) { high = Arrays.binarySearch(numbers, target); high = high >= 0 ? high : -high - 1; } else if (numbers[high] <= 0 && target > numbers[low]) { low = Arrays.binarySearch(numbers, target); low = low >= 0 ? low : -low - 1; } while (low < high) { int sum = numbers[low] + numbers[high]; if (sum == target) { return new int[]{low + 1, high + 1}; } if (sum > target) { high--; } else { low++; } } throw new IllegalArgumentException("No solution exists"); } }

public class Solution { public int[] twoSum(int[] numbers, int target) { int lo = 0, hi = numbers.length-1; int sum = numbers[lo] + numbers[hi]; while(numbers[lo] + numbers[hi] != target) if (numbers[lo] + numbers[hi] > target) hi--; else lo++; return new int[] {lo+1, hi+1}; } }

public class Solution { public int[] twoSum(int[] numbers, int target) { int ans[] = new int [2]; int p1 = 0; int p2 = numbers.length-1; while(p1 < p2) { int sum = numbers[p1] + numbers[p2]; if(sum == target) { ans[0] = p1 + 1; ans[1] = p2 + 1; break; } else if (sum < target) p1++; else p2--; } return ans; } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。