输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数

[问答题]

输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和是输入的那个数字，要求时间复杂度为O(n)，如果有多对数字的和等于输入的数字，输出任意一对即可。

⎝≧⏝⏝≦⎠|

private static void findAns(int[] data, int sum) {
    int size = data.length;
    int begin = 0;
    int end = size-1;
    while (begin < size && end >=0 && begin < end) {
        int cu = data[begin] + data[end];
        if (cu > sum) {
            end --;
        } else if (cu < sum) {
            begin ++;
        } else {
            System.out.println(data[begin] + " " + data[end]);
            return;
        }
    }
    System.out.println("无匹配项");
}

发表于 2017-07-30 10:37:54 回复(0)

王占伟

publicvoidfind(int[] a,inttarget){
    intsmall=0;
    intbig=a.length-1;
    while(small<big){
         if(a[small]+a[big]>target){
             big--;
          }
          if(a[small]+a[big]<target){
              small++;
          }
          if(a[small]+a[big]==target){
              System.out.println(a[small]+" "+a[big]);
                break;
          }
    }
}

因为是升序排列
两个标志位，最小值small，和最大值big.
如果最小值的位置加最大值的位置和大于目标值，说明big值太大了，所以--
如果最小值位置加最大值位置小于目标值，说明small值太小
所以++
直到找到或没找到

编辑于 2017-08-01 11:39:47 回复(0)

眉毛密过发

public int[] findSumToNum(int[] nums,int target){
    Map<Integer,Integer> map=new HashMap<>();
    for(int i=0;i<nums.length;i++){
        if(map.containsKey(target-nums[i])){
            return new int[]={map.get(target-nums[i],i)};                             
        }
        else map.put(nums[i],i);
    }
    return new int[]={};
}

发表于 2019-09-23 00:13:06 回复(0)

2333333333333333

二分查找

发表于 2018-03-20 10:17:22 回复(0)

疯癫201712091243147

数组设为arr，目标数设为num 则，for(int i=0;i<arr.lenght;i++){ int a=num-arr[i]; if(a==arr[i]) System.out.println(arr[i]) }

发表于 2017-12-17 01:38:15 回复(0)

Holiday_12138

哈希表

发表于 2017-08-01 15:12:43 回复(1)

onlymy

对一楼的稍加修改

public class FindSUm {

    public static void main(String[] args){ int[] a={1,2,3,4,5,6};  int b = 9;  findSum(a,b);  } public static void findSum(int[] data,int sum){ int size = data.length;  int end = size-1;  int begin = 0;  while (begin<size && end>=0 && begin<end){ int cu =data[begin] + data[end];  if (cu<sum){
                begin++;  }else if(cu>sum){
                end--;  }else{
                System.out.println(data[begin]+" "+data[end]);  end--;  begin++;  }
        }

    }
}

发表于 2017-08-01 10:20:31 回复(0)

feelinghappy

#include <assert.h>
#include <iostream>
using namespace std;
bool OutputProperlyValue(const int *pA, int nSize, int nKey)
{
assert(NULL != pA || nSize > 0);
int i32First = 0, i32End = nSize - 1;
for (; i32First < i32End; )
{
if (pA[i32End] >= nKey)
{
i32End--;
}
else if ((pA[i32End] + pA[i32First]) < nKey)
{
i32First++;
}
else if ((pA[i32End] + pA[i32First]) > nKey)
{
i32End--;
}
else
{
cout << "两个元素和为" << nKey << "的值的数组元素为：" << pA[i32First] << "和" << pA[i32End] << endl;
break;
}
}
if (i32First >= i32End)
return false;
return true;
}
int _tmain(int argc, _TCHAR* argv[])
```
{  
```
int aryT[] = {1, 2, 4, 7, 11, 15};
if (!OutputProperlyValue(aryT, (sizeof(aryT)/sizeof (int)), 14))
{
cout << "数组里没有合适的值" << endl;
}
```
    return 0;  
```
```
}  
```