剑指offer-在数组中查找两个数,是的他们的和正好是S(一次性跑通)(时间复杂度还可以降低)

剑指offer-在数组中查找两个数,是的他们的和正好是S(一次性跑通)(时间复杂度还可以降低)

/*对于一个递增的序列,存在2个数字的和相等,要想这2个数字的乘积最小,则这2个数字的距离最远*/
/*思想:j指向最后一个元素,然后i从前扫描看sum-a[j]在这个序列中吗?若不在j--*/

剑指offer-在数组中查找两个数,是的他们的和正好是S(一次性跑通)(时间复杂度还可以降低)


剑指offer-在数组中查找两个数,是的他们的和正好是S(一次性跑通)(时间复杂度还可以降低)

import java.util.ArrayList;
public class Solution { static boolean binSearch(int a[],int key){
int low=0,high=a.length-1;
while(low<=high){
int mid = (low+high)/2;
if(a[mid] == key) return true;
else if (a[mid]<key) low = mid+1;
else high = mid-1;
}
return false;
} public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { ArrayList<Integer> list = new ArrayList<Integer>();
int flag=-1;int cheng ; int leizhu = 999999999;
for(int i=0;i<array.length;i++){
if(binSearch(array,sum-array[i]) && array[i]!=sum-array[i])
{   
          cheng = array[i]*(sum-array[i]);
  if(cheng<leizhu) leizhu= cheng; flag=i;}
}
if(leizhu==999999999) return list;
list.add(sum-array[flag]);
list.add(array[flag]);
return list;
}
}
上一篇:EF是啥?【What is Entity Framework?】(EF基础系列2)


下一篇:B站视频怎么下载到本地【实用教程】