首页 > 试题广场 >

和为S的两个数字

[编程题]和为S的两个数字

热度指数：490379 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

数据范围: $0 \le len(array) \le 10^5 \$ ， $1 \le array[i] \le 10^6 \$

示例1

输入

[1,2,4,7,11,15],15

输出

[4,11]

说明

返回[4,11]或者[11,4]都是可以的

示例2

输入

[1,5,11],10

输出

[]

说明

不存在，返回空数组

示例3

输入

[1,2,3,4],5

输出

[1,4]

说明

返回[1,4],[4,1],[2,3],[3,2]都是可以的

示例4

输入

[1,2,2,4],4

输出

[2,2]

算法知识视频讲解

推荐

马客(Mark)

数列满足递增，设两个头尾两个指针i和j，

若ai + aj == sum，就是答案（相差越远乘积越小）

若ai + aj > sum，aj肯定不是答案之一（前面已得出 i 前面的数已是不可能），j -= 1

若ai + aj < sum，ai肯定不是答案之一（前面已得出 j 后面的数已是不可能），i += 1

O(n)

typedef vector<int> vi;
class Solution {
public:
    vi FindNumbersWithSum(const vi& a,int sum) {
        vi res;
        int n = a.size();
        int i = 0, j = n - 1;
        while(i < j){
            if(a[i] + a[j] == sum){
                res.push_back(a[i]);
                res.push_back(a[j]);
                break;
            }
            while(i < j && a[i] + a[j] > sum) --j;
            while(i < j && a[i] + a[j] < sum) ++i;
        }
        return res;
    }
};

编辑于 2016-08-03 15:52:48 回复(80)

Java

SUMMERENT

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                if (array[i] + array[j] == sum && i != j) {
                    list.add(array[i]);
                    list.add(array[j]);
                    return list;
                }
            }
        }
        return list;
    }
}

发表于 2023-06-15 10:15:13 回复(0)

Java

酷鹿路的跟屁虫

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        int n =array.length;
        if(n < 2) return ans;
        int left = 0, right = n - 1;
        while(left < right && left < n && right < n){
            if(array[left] + array[right] > sum) {
                right--;
            }else if(array[left] + array[right] < sum){
                left++;
            }else{
                ans.add(array[left]);
                ans.add(array[right]);
                break;
            }
        }
        return ans;
    }
}

发表于 2023-03-08 21:13:33 回复(0)

Java

lmghzzq

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> a =new ArrayList<>();
        int i=0,j=array.length-1;
        while(i<j){
            if(array[i]+array[j]==sum){
                a.add(array[i]);
                a.add(array[j]);
                break;
            }
            if(array[i]+array[j]>sum) j--;
            if(array[i]+array[j]<sum) i++;
        }
        return a;
    }
}

发表于 2022-10-13 18:09:11 回复(0)

Java

肥咩咪

//和数组的排序有点像
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list=new ArrayList<>();
        if(array==null||array.length<2){
            return list;
        }

        int l=0;
        int r=array.length-1;
        while(r>l){
            int s=array[l]+array[r];
            if(s==sum){              
                break;
            }else if(s>sum){
                r--;
            }else{
                l++;
            }
        }

        if(array[l]+array[r]==sum){
            list.add(array[l]);
            list.add(array[r]);
        }

        return list;       
    }
}

发表于 2022-09-19 23:45:37 回复(0)

Java

是小王吖🐅

import java.util.*;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int end_cur=array.length-1;
        while(end_cur>=0){
            if(array[end_cur]>=sum){
                end_cur--;
            }else{
                break;
            }
        }
        ArrayList<Integer> rst=new ArrayList<>();
        //确定了数组取值的
        label1:for(int cur=end_cur;cur>=0;cur--){
            for(int cur_1=0;cur_1<cur;cur_1++){
                if(array[cur]+array[cur_1]==sum){
                    rst.add(array[cur]);
                    rst.add(array[cur_1]);
                    break label1;
            }
        }
    }
        return rst;
}
}

发表于 2022-08-26 17:28:43 回复(0)

Java

NorthXwind

双指针

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int l = 0;
        int r = array.length - 1;
        while (l < r) {
            int temp = array[l] + array[r];
            if (temp < sum) {
                l++;
            } else if (temp > sum) {
                r--;
            } else {
                res.add(array[l]);
                res.add(array[r]);
                break;
            }
        }
        return res;
    }
}

发表于 2022-06-17 15:28:47 回复(0)

Java

浮鸟(BAT实习ing，目标外企~)

一上来直接双指针过了，然后看了题解才想起来用hashmap也可以

解法1：双指针

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        // 两个指针：一头一尾
        
        // 定义返回
        ArrayList<Integer> ret = new ArrayList<Integer>();
        // 边界值
        if(array.length==0 || array == null)
            return ret;
        
        // 定义双指针
        int left=0;
        int right=array.length-1;
        // 循环判定
        while(left<right){
            // 如果两个指针所指数字和大于sum，则right指针左移
            if(array[left]+array[right]>sum){
                right-=1;
            }
            // 如果两个指针所指数字和小于sum，则left指针右移
            else if(array[left]+array[right]<sum){
                left+=1;
            }
            // 如果刚好等于，记录，返回
            else{
                ret.add(array[left]);
                ret.add(array[right]);
                return ret;
            }
        }
        
        return ret;
    }
}

解法2：哈希（找了一圈好像没java版本的题解，我直接发一个）

import java.util.*;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        // 哈希法
        
        // 定义返回
        ArrayList<Integer> ret = new ArrayList<Integer>();
        // 边界
        if(array.length==0||array==null){
            return ret;
        }
        // 定义hashmap
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        // 边循环，边记录，边判定
        for(int i=0;i<array.length;i++){
            // 如果map已经记录过b的value了，说明b作为a出现过
            if(map.containsKey(array[i]) && map.get(array[i]) == sum-array[i]){
                ret.add(sum-array[i]);
                ret.add(array[i]);
                return ret;
            }
            
            // 存储时候和if判定的顺序调过来，key是b，value是a
            map.put(sum-array[i],array[i]);
        }
        
        return ret;
    }
}

发表于 2022-02-02 14:53:30 回复(0)

Java

Beecy

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        if (array.length == 0 || sum == 0)
            return list;
        for (int i = 0; i < array.length; i++){
            int temp = sum - array[i];
            if (list.isEmpty()){
                for (int j = i + 1; j < array.length; j++){
                    if (temp == array[j]){
                        list.add(array[i]);
                        list.add(array[j]);
                    }
                }
            }
        }
        return list;
    }
}

发表于 2021-12-16 17:16:56 回复(0)

Java

空中转体一周半

来个复杂版本：设计一个类，用于对map映射。
然后其操作就是两数之和。空间o(n),时间o(n)...

import java.util.*;
public class Solution {
    private class Num{
        int base;
        int time;
        Num(int base){
            this.base = base; 
            this.time = 1;
        }
     void setTime(int time){
            this.time = time;
        }
      int getTime(){
          return this.time;
      }
    }
    public ArrayList FindNumbersWithSum(int [] array,int sum) {
         ArrayList res = new ArrayList();
         ArrayList > resArray = new ArrayList();
         Map kv = new HashMap();
         for(int i=0;i<array.length;++i){
             Num num = new Num(array[i]);
             if(kv.get(array[i])!=null){
                 Num temp = kv.get(array[i]);
                 int t = temp.getTime();
                 temp.setTime(++t);
             }
             else
               kv.put(array[i],num);
         }
         for(int i=0;i<array.length;++i){
             if(kv.get(array[i])!=null&&kv.get(sum-array[i])!=null){
                 Num temp = kv.get(array[i]);
                 int t = temp.getTime();
                 if(t>1){
                     temp.setTime(--t);
                 }
                 else 
                     kv.remove(array[i]);
                 if(kv.get(sum-array[i])!=null){
                     ArrayList tempa = new ArrayList();
                     tempa.add(array[i]);
                     tempa.add(sum-array[i]);
                     resArray.add(tempa);
                 }
             }
         }
        int  k,v,mul;
        if(resArray.size()==0)return res;
        else {
            k = resArray.get(0).get(0);
            v = resArray.get(0).get(1);
            mul = k*v;
        }
        for(int i=0;i<resArray.size();++i){
            int t1 = resArray.get(i).get(0);
            int t2 = resArray.get(i).get(1);
            if(mul> t1*t2)
            {   k = t1;
                v = t2;
                mul=k*v;
            }
        }
        res.add(k);res.add(v);
        return res;
    }
}

发表于 2021-09-23 14:36:06 回复(0)

Java

派大星攻城狮

离大谱解法，单独处理多对的情况

import java.util.*;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int n = array.length;
        ArrayList<Integer> ans = new ArrayList<Integer>();
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < n;i++){
            if(map.containsKey(sum-array[i])){
                ans.add(sum-array[i]);
                ans.add(array[i]);
            }
            map.put(array[i],i);
        }
        int min = Integer.MAX_VALUE,index = 0,index1 = 1;
        if(ans.size() > 2){
            for(int i = 0;i < ans.size()-1;i+=2){
                if(ans.get(i)*ans.get(i+1) < min){
                    min = ans.get(i)*ans.get(i+1);
                    index = i;
                    index1 = i+1;
                }
            }
            ArrayList<Integer> res = new ArrayList<Integer>();
            res.add(ans.get(index));
            res.add(ans.get(index1));
            return res;
        }
        return ans;
    }
}

发表于 2021-09-21 21:37:29 回复(0)

Java

God3

import java.util.*;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int cur = 0;
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        ArrayList<Integer> res = new ArrayList<>();
          for (int i = 0; i < array.length; i++) {
            if (ans.contains(sum - array[i])) {
                cur = array[i] * (sum - array[i]);
                list.add(sum - array[i]);
                list.add(array[i]);
            }
            ans.add(array[i]);
        }
        if (list.size() == 0) return new ArrayList<>();
        res.add(list.get(list.size() - 2));
        res.add(list.get(list.size() - 1));
        return res;
    }
}

发表于 2021-09-08 15:11:38 回复(0)

Java

624huiguorou

/*
思路：
1.有序2.两个数
所以天然的首位双指针，low和high。
和小了，low右移。和大了，high左移。

low从前往后找，第一个就是乘积最小的。
简单的证明：
x*y最小。x+y=s。所以y=s-x。
x*y=x*(s-x)=-x^2-s*x。
为关于x的开口向下的抛物线。所以最小值就是x最小的时候取得。
也就是low从前往后第一个符合条件的结果。

    /*
    思路：
    1.有序2.两个数
    所以天然的首位双指针，low和high。
    和小了，low右移。和大了，high左移。
    
    low从前往后找，第一个就是乘积最小的。
    简单的证明：
    x*y最小。x+y=s。所以y=s-x。
    x*y=x*(s-x)=-x^2-s*x。
    为关于x的开口向下的抛物线。所以最小值就是x最小的时候取得。
    也就是low从前往后第一个符合条件的结果。
    */
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> resList = new ArrayList<>();
        int low = 0,high = array.length-1,lastProduct = 1;
        while(low < high){
            int nowSum = array[low] + array[high];
            if(nowSum < sum){
                low++;
            }else if(nowSum > sum){
                high--;
            }else{
                //low从前往后找，第一个就是乘积最小的。
                resList.add(array[low]);
                resList.add(array[high]);
                break;
            }
        }
        return resList;
    }

发表于 2021-08-30 17:40:08 回复(0)

Java

QAQWQAQ

public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        int left = 0;
        int right = array.length - 1;
        ArrayList<Integer> integers = new ArrayList<>();
        while (left < array.length && right >= 0 && right > left) {
            int ans = array[left] + array[right];

            if (ans == sum) {
                integers.add(array[left]);
                integers.add(array[right]);
                break;
            } else if (ans > sum) {
                right--;
            } else {
                left++;
            }
        }
        return integers;
    }

发表于 2021-08-24 17:41:44 回复(0)

Java

ncc2814

import java.util.*;

public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        if(array == null || array.length == 0) {
            return new ArrayList<>(0);
        }
        Integer x = null, y = null;
        ArrayList<Integer> ans = new ArrayList<>();
        int i = 0, j = array.length-1;
        int multiply = Integer.MAX_VALUE;
        while(i < j) {
            if(array[i] + array[j] == sum) {
                int temp = array[i] * array[j];
                if(temp < multiply) {
                    multiply = temp;
                    x = array[i];
                    y = array[j];
                }
                i++;
            } else if(array[i] + array[j] < sum) {
                i++;
            } else {
                j--;
            }
        }
        if(x == null || y == null) {
            return ans;
        }
        ans.add(x);
        ans.add(y);
        return ans;
    }
}

发表于 2021-08-11 21:44:44 回复(0)

Java

烫杯藕粉

评论区中已经说了，和为sum的最外围的两个数就是乘积最小的。

证明：首先a+b=sum,a<b

所以有

(a+1)(b-1) = sum

=ab+(b-a)+1,因为b-a>0,且必为整数所以b-a>=1

>=ab;

以此向内推算所有内部的都小于等于ab

（证明：）

(a+k)(b-k) = sum

=ab +kb -ak -k*k

=ab +(b-a)k - k*k

a和b之间的元素个数肯定大于k，而且因为左指针小于右指针需要（a+k）< (b-k) 所以就是

b-a>2k,

那么（b-a）*k>2*k*k

所以 ab <= (a+k)(b-k)

使用头尾指针逼近的方法。

1，当前left+right<sum:left++

2，当前left+right>sum:right--

3，当前left+right==sum：break

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(null == array || array.length==0) return result;
        //双指针解法
        int left = 0;
        int right = array.length-1;
        //左右指针逼近
        while(left<right){
            int cur = array[left]+array[right];
            if(cur < sum){
                left++;
            }else if(cur > sum){
                right--;
            }else{
                result.add(array[left]);
                result.add(array[right]);
                break;
            }
        }
        return result;
    }
}

发表于 2021-08-11 15:56:55 回复(0)

Java

牛客慧

//两个数离得越近，乘积越大，所以外层乘积小于内层乘积
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list=new ArrayList<>();
        int i=0;
        int j=array.length-1;
        while(i<j){
            if(array[i]+array[j]<sum){
                i++;
            }else if(array[i]+array[j]>sum){
                j--;
            }else{
                list.add(array[i]);
                list.add(array[j]);
                break;
            }
        }
        return list;
    }
}

发表于 2021-08-08 12:18:46 回复(0)

Java

可爱朋友

import java.util.ArrayList;
import java.util.*;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> a = new ArrayList<Integer> (2);
        Arrays.sort(array);
        int temp1 = 0;
        int temp2 = 0;
        int flag = 0;
        for(int i = 0; i<array.length; i++){
            for(int j = i+1;j<array.length;j++){
                if(array[i]+array[j]==sum && flag==0){
                    temp1 = array[i];
                    temp2 = array[j];
                    flag++;
                    break;
                }
            }
        }
        if(temp1!=0&&temp2!=0){
          a.add(temp1);
          a.add(temp2);
          return a;  
        }else
            return a;
        
    }
}

很简单哦~

发表于 2021-08-06 17:13:32 回复(0)

Java

一刀一个小盆友亜

Java用hashmap实现

import java.util.*;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        HashMap map=new HashMap();
        ArrayList<Integer> a=new ArrayList<Integer>();
        for(int i=0;i<=array.length-1;i++){
            if(map.get(sum-array[i])!=null){//hashmap查重
                while(!a.isEmpty()){//每次清空map，因为是有序，所以最后满足条件的总是乘积最小的
                    a.remove(0);
                }
                a.add(sum-array[i]);
                a.add(array[i]);
            }
            map.put(array[i],i);
        }
        return a;
    }
}

发表于 2021-08-03 19:49:04 回复(0)

Java

^ǒ^月亮船^

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> result = new ArrayList<>();
        
        //超过这个值，后面不会再出现匹配的组合了
        int mid = sum/2 + 1;
        
        for(int i = 0; i < array.length ; i++){
            if(array[i] > mid){
                return result;
            }
            
            int num = sum - array[i];
            
            for(int j = array.length - 1 ; j > i; j--){
                if(array[j] < num){
                    break;
                }else if(array[j] == num){
                    //从小到大找，乘积最小的组合就是最早发现的组合
                    result.add(array[i]);
                    result.add(array[j]);
                    return result;
                }
            }
        }
        
        return result;
    }
}

发表于 2021-08-03 14:35:50 回复(0)

提交观点

问题信息

数组数学双指针

来自：“一战通offer”互...

难度：

177条回答 810收藏 97512浏览

通过挑战的用户

查看代码

Elastic...

2023-02-25 22:47:48
牛客71194...

2022-09-16 15:27:36
大金毛_

2022-09-16 11:30:22
远方不姓方

2022-09-16 10:39:10
ৡ晨ꦿ᭄࿐

2022-09-16 09:49:19

和为S的两个数字

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题