给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,_美团笔试题

大漠孤狼

答案：O(n)

思想类似于两端向中间扫描

1、设定两个指针P1、P2，分别指向数组开始和结尾，即P1指向最小值，P2指向最大值；

2、计算 *P1+*P2 的值为 SUM，与 sum 比较，记录它们的差值 DIF 和 SUM，若 SUM<sum，P1++，若SUM>sum，P2--;

3、重复以上过程直到DIF最小

发表于 2015-09-29 16:46:08 回复(4)

这个好玩吗？

可以参考《剑指Offer》

发表于 2017-03-05 09:35:40 回复(0)

sunwuyi

链接：https://www.nowcoder.com/questionTerminal/d5a859566bab460a8a9f56ad16800640?source=relative
来源：牛客网

答案：O(n)

思想类似于两端向中间扫描

1、设定两个指针P1、P2，分别指向数组开始和结尾，即P1指向最小值，P2指向最大值；

2、计算 *P1+*P2 的值为 SUM，与 sum 比较，记录它们的差值 DIF 和 SUM，若 SUM<sum，P1++，若SUM>sum，P2--;

3、重复以上过程直到DIF最小

发表于 2018-10-12 08:41:24 回复(0)

周强

有序线性表中查找两个数：

1. 设置两个指针分别从头部和尾部向中间扫描（*head *tail）

2. 将两数的和和sum比较，（*head+*tail）< sum head++;反之tial--,若两数的和刚好等于sum 直接退出循环

发表于 2015-12-23 17:03:50 回复(0)

sunlight_run

设置两个指针，指向首、尾两元素。如果和大于sum就将后端指针左移，如果和小于sum，就将前端指针右移！

发表于 2017-06-30 11:12:22 回复(1)

DQ_DM

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

void FindClosestPair(int *a,int n,int sum)
{
    int i=0,j=n-1;
    int dif=INT_MAX;
    int Start=0,End=0; //存储输出的元素
    while(i<n&&j>i)
    {
        if(abs(a[i]+a[j]-sum)<dif)
        {
            Start=a[i];
            End=a[j];
            dif=abs(a[i]+a[j]-sum);
        }
        else if(a[i]+a[j]<sum)
        { //若当前差值依然是最小的，并且两数之和比期望值小，
          //说明应该增大左边的值
            i++;
        }
        else
        {
            j--;
        }
    }
    cout<<Start<<" "<<End<<endl;
}


int main()
{
    int a[]={-5,-1,0,1,4,5,7,9};
    FindClosestPair(a,8,8);
    return 0;
}

发表于 2015-10-05 10:52:19 回复(2)

grass_stars

应该为O（n）时间，2个指针从数组的开始位置和结束位置移动，和小于sum，left++，和大于sum，right--。更新最小的差值，和2个指针的值，移动时更新。差值为0，则停止。

编辑于 2016-07-09 10:47:27 回复(2)

夏伤

取sum/2，对数组二分查找，找到与sum/2最接近的整数，如果其小于sum/2则与其右边一个数的和最接近sum，反之则与左边第一个数的和最接近sum。对于1 6 7 12 sum=12的情况也适合。由于数组本身有序，所以这样进行二分查找可以在logn的时间内完成查找。不一定是唯一的答案，但已经找到了，题目并没有要求找出所有满足条件的ab组合，只要求最快找到这样的ab

发表于 2016-11-05 20:31:46 回复(3)

ssthouse

/**

* 题目:

* 给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最快的平均时间复杂度是：

* Created by ssthouse on 2016/3/23.

*/

public class FindSumClosest {

//找出差别最小的差值

public static void getClosestDiff(int[] array, int value) {

//初始指针指向左右初始值指向左右的数字

int leftIndex = 0, rightIndex = array.length - 1;

int resultLeft = array[0], resultRight = array[array.length - 1];

//初始化最小差值

int minDiffer = Math.abs(resultLeft + resultRight - value);

//分别向左右遍历整个数组

while (leftIndex < array.length && rightIndex >= 0) {

int currentSum = array[leftIndex] + array[rightIndex];

//如果差别更小---更新左右数字

if (Math.abs(currentSum - value) < minDiffer) {

resultLeft = array[leftIndex];

resultRight = array[rightIndex];

}

if (currentSum == value) {

break;

} else if (currentSum < value) {

leftIndex++;

} else {

rightIndex--;

}

System.out.println(resultLeft + ":" + resultRight);

}

//测试main

public static void main(String[] args) {

System.out.println("Hello World!");

int testArray[] = {1, 3, 4, 5, 6, 7, 8, 9};

FindSumClosest.getClosestDiff(testArray, 4);

}

编辑于 2016-03-23 11:23:51 回复(2)

等待再次绽放~

以sum/2为中间值进行二分查找

发表于 2015-09-28 14:21:34 回复(3)

嘉祐

摘自：http://www.cnblogs.com/boring09/p/4230707.html

假设存在number [i] + number [j] = target（i < j）。

head在什么情况下可能移动到i的右边？假设head已经移动到了i的右边，即head > i且numbers [head] > numbers [i] ，根据算法规则，只有当numbers [head] + numbers [tail] < target时，head才会右移，所以 numbers [tail] < target - numbers [head] < target - numbers [i] = numbers [j] ，意味着tail一定出现在j的左边。

那tail在什么情况下可能移动到j的左边？同理，只有当head在i的右边时才可能发生。

因为一开始head在i的左边，tail在j的右边，算法每次只移动head或tail，所以不可能出现某一时刻经过算法移动后，head移动到i的右边而同时tail移动到j的左边的情况。证明结束。

发表于 2016-10-02 16:35:26 回复(0)

ploughthough

双指针法

发表于 2023-12-03 19:58:55 回复(0)

GoAshore

设置两个指针，指向首、尾两元素。如果和大于sum就将后端指针左移，如果和小于sum，就将前端指针右移

发表于 2022-12-06 20:58:09 回复(0)

Wilbur.

居然不能二分

发表于 2022-08-25 19:30:11 回复(0)

牛客305103867号

如果元素之间的差值不全都是1，有大有小怎么办

发表于 2021-05-08 08:17:54 回复(0)

牛客818246740号

两端像中间找

发表于 2020-06-28 12:14:47 回复(0)

呐1呐1呐

设置两个指针，指向首、尾两元素。如果和大于sum就将后端指针左移，如果和小于sum，就将前端指针右移！

发表于 2020-02-29 17:46:25 回复(0)

可爱的小孩儿

O(blown)的复杂度高于线性低于平方

发表于 2019-11-25 09:59:53 回复(0)

菜🐔也要有梦

 public void minDiff(int[] nums, int sum) {

        int low = 0;
        int high = nums.length - 1;
        int diff = Integer.MAX_VALUE;
        int a = 0;
        int b = 0;

        while (low < high) {
            if (Math.abs(nums[low] + nums[high] - sum) < diff) {
                diff = Math.abs(nums[low] + nums[high] - sum);
                a = nums[low];
                b = nums[high];
            } else if (nums[low] + nums[high] > sum) {
                high --;
            } else {
                low ++;
            }
        }

        System.out.printf("a,b is %d, %d", a, b);
    }

发表于 2019-09-27 22:15:01 回复(0)

寂静于暖

public class ABSum {

    public static void main(String[] args) {
        int[] nums = {-5, -1, 0, 1, 4, 5, 7, 9};
        getAB(nums, 6);
        int[] nums2 = {1, 3, 4, 5, 6, 7, 8, 9};
        getAB(nums2, 4);
    }

    public static void getAB(int[] nums, int sum) {
        int left = 0, right = nums.length - 1;
        int dif = Integer.MAX_VALUE;
        while(left < nums.length - 1 && left < right) {
            if(dif > Math.abs(nums[left] + nums[right] - sum)) {
                dif = Math.abs(nums[left] + nums[right] - sum);
            }
            if(dif == 0) {
                break;
            }
            if(nums[left] + nums[right] > sum) {
                right--;
            }else {
                left++;
            }
        }
        System.out.println(nums[left] + " " + nums[right]);
    }
}

编辑于 2019-04-02 11:25:19 回复(0)

给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,

问题信息

热门推荐

相关试题