You may assume that each input would have exactly one solution and you may not use the same element twice.
给定一个已经按照升序排序的整数数组,找到两个数字,这样它们就会加到一个特定的目标号上。
函数两个和应该返回两个数字的索引,这样它们就会加到目标上,在这个位置上,index1必须小于非定数。请注意,您返回的答案(包括index1和index2)并不是基于零的。
您可以假设每个输入都有一个正确的解决方案,并且您可能不使用相同的元素两次
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
对于一个有序数组,进行这样的算法操作,其实还是非常简单的,首先想到的就是暴力。进行两次for循环搜索,将不同的数组值相加,直到相等为止,继而输出数组下标即可。
暴力代码如下;
public class Solution { public int[] twoSum(int[] numbers, int target) { int i=0; int j=0; while(numbers[i]<target&&i<numbers.length-1) { i++; } j=i; for(int k=0;k<=j;k++) { for(int n=k+1;n<=j;n++) { if(numbers[n]+numbers[k]==target) return new int[]{k+1,n+1}; } } return new int []{1,2}; } }但是,这样的暴力算法却超时了。因此没有办法,必须想出另外一种解决办法。
超时之所以超时,无非是遍历时循环次数太多造成的,故此可以想到使用二分查找法来解决问题。(注意使用其,必须确保数组是排序数组)
大体思想:
两个指针,一个指向头,另外一个指向尾,即num[0]、num[num.length-1],二者做相加运算,此时将会产生三种情况:大于,小于,等于 。其中最简单的便是等于情况。直接返回数组下标即可。那么大于和小于便就是要使用二分法的时候了,可以略作思考,大于情况时,下一步怎么处理?
将相加运算的值减小!所以只需移动尾指针向前。同理,小于情况时,只需要头指针向后。那么移动一次,依旧不满足呢?再移动?那要是n次都不满足呢?故此,便要使用二分法。
那么就本次使用的二分法进行简单的扩展:
如果target<num[m]+num[n]=value,这时需要尾指针前移,
那么我只需要找出num[n]=target-num[m]即可,那么同理当target>num[m]+num[n]也只需要找到num[m]=target-num[n]即可
因此算法如下:
public class Solution { public int[] twoSum(int[] numbers, int target) { int start = 0; int end = numbers.length - 1; while(start < end){ int value = numbers[start] + numbers[end]; if(value < target){ start = binarySearch(numbers, start + 1, end -1, target - numbers[end]); }else if(value > target){ end = binarySearch(numbers, start + 1, end - 1, target - numbers[start]); }else if(value == target){ return new int[]{start + 1, end + 1}; } } throw new RuntimeException("not found!"); } public int binarySearch(int[] nums, int start, int end, int target){ while(start < end){ int mid = (start + end)/2; if(nums[mid] == target){ return mid; }else if(nums[mid] < target){ start = mid + 1; }else if(nums[mid] > target){ end = mid - 1; } } return start; } } 如果不适用二分法思想也是可以的,下面一组程序便是使用前后指针来查找。 public class Solution { public int[] twoSum(int[] numbers, int target) { int m=0; int n=numbers.length-1; for(int k=0;k<=numbers.length;k++) { if(numbers[m]+numbers[n]==target) { return new int []{m+1,n+1}; } if(numbers[m]+numbers[n]<target) { m++; n=n; } if(numbers[m]+numbers[n]>target) { m=m; n--; } } //此处随意返回即可 return new int []{1,2}; } }