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

//开始还在纠结乘积最小，后来转念一想，a+b=sum,a和b越远乘积越小，而一头一尾两个指针往内靠近的方法找到的就是乘积最小的情况。如果是乘积最大的情况就是一直找到两个指针重合，每次找到一个就将之前返回的结果向量清空然后更新为新找到的。
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> result;
        int length = array.size();
		int start = 0;
		int end = length - 1;
		while (start < end)
		{
			if (array[start] + array[end] == sum)
			{
				result.push_back(array[start]);
                result.push_back(array[end]);
				break;
			}
			else if (array[start] + array[end] < sum)
				start++;
			else
				end--;
		} 
        return result;
    }
};

def FindNumbersWithSum(self, array, tsum):
    # 两头开始找匹配，乘积最小必定为最先找到的，如7+8=15 1+14=15乘积1*14小
    low, high = 0, len(array) - 1
    while low < high:
        if array[low] + array[high] > tsum:
            high -= 1
        elif array[low] + array[high] < tsum:
            low += 1
        else:
            return [array[low], array[high]]
    return []  # 匹配失败返回空list

    def FindNumbersWithSum(self, array, tsum):
        couple = [tsum-i for i in array]
        filtarray = [i for i in array if i in couple]
        try:
            return [filtarray[0],filtarray[-1]]
        except:
            return []

python solution:

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        for i in array:
            if tsum-i in array:
                if tsum-i==i:
                    if array.count(i)>1:
                        return [i,i]
                else:
                    return [i,tsum-i]
        return []

//双指针
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> ret;
        int i = 0, j = array.size()-1;
        while(i < j){
            if(array[i] + array[j] == sum){
                if(ret.empty()){
                    ret.push_back(array[i]);
                    ret.push_back(array[j]);
                }
                else if(array[i]*array[j] < ret[0]*ret[1]){
					ret[0] = array[i];
                    ret[1] = array[j];
                }
                ++i;
                --j;     
            }
            else if(array[i] + array[j] < sum) ++i;
            else --j;           
        }
        return ret;
    }
};

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
		int l=0,h=array.length-1;
		ArrayList<Integer> list=new ArrayList<>();
		if(array==null||array.length<2||sum<=2) return list;
		int currentSum=array[l]+array[h];
		int minMult=Integer.MAX_VALUE;
		while(l<h){
			if(currentSum==sum){
				//多个时判断是否乘积最小
				if(minMult>array[l]*array[h]){
					list.clear();
					list.add(array[l]);
					list.add(array[h]);
					minMult=array[l]*array[h];
				}
				//不管是不是最小都要进行i++和h--
				l++;h--;
			}else if(currentSum<sum){
				l++;
			}else {
				h--;
			}
			currentSum=array[l]+array[h];
		}
		return list;
    }
}

/*
*你们都写复杂啦，其实可以证明：当a1<=a2<=b2<=b1,然后又a1+b1 = a2+b2时，则一定有*a1*b1<=a2*b2的，无论正负。所以只需按照正常的思路找到第一个解就行了。
*/

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

剑指Offer-和为S的两个数字

package Array;
import java.util.ArrayList;
import java.util.HashMap;
/**
 * 和为S的两个数字
 * 输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
 * 对应每个测试案例，输出两个数，小的先输出。
 */
public class Solution34 {
    public static void main(String[] args) {
        Solution34 solution34 = new Solution34();
        int[] array = {1, 2, 3, 4, 5, 6};
        int sum = 5;
        System.out.println(solution34.FindNumbersWithSum_2(array, sum));
    }
    /**
     * 两头夹逼
     *
     * [@param array
     * @param sum
     * @return](/profile/547241) */
    public ArrayList FindNumbersWithSum(int[] array, int sum) {
        ArrayList result = new ArrayList();
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            if (array[left] + array[right] == sum) {
                result.add(array[left]);
                result.add(array[right]);
                break;
            } else if (array[left] + array[right] > sum) {
                right--;
            } else {
                left++;
            }
        }
        return result;
    }
    /**
     * 用HashMap存放元素和下标，然后开始遍历数组找到和为sum的两个元素，从左到右找到的第一对和为sum的就是最小的一对。
     *
     * [@param array
     * @param sum
     * @return](/profile/547241) */
    public ArrayList FindNumbersWithSum_2(int[] array, int sum) {
        HashMap map = new HashMap();
        ArrayList result = new ArrayList();
        int len = array.length;
        for (int i = 0; i < len; i++) {
            map.put(array[i], i);
        }
        for (int i = 0; i < len; i++) {
            int sub = sum - array[i];
            if (map.containsKey(sub)) {
                result.add(array[i]);
                result.add(sub);
                break;
            }
        }
        return result;
    }
}

	# -*- coding:utf-8-*-



	classSolution:



	def FindNumbersWithSum(self, array, tsum):



	couple = [tsum - i for i in array]



	result = [i for i in array if i in couple]



	try:



	returnresult[0],result[-1]



	except:



	return[]

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        s = tsum
        sums = {}
        res1 = 999
        res2 = 999
        for x in array:
                 sums[x] = s - x
        for x in sums.keys():
            if x in sums.values() and x != sums[x]:
                res1 = x
                res2 = sums[x]
        if res1 not in array:
            return []
        if res1 < res2:
            return res1,res2
        else:
            return res2,res1        

	



	# -*- coding:utf-8 -*-

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        if array is None or len(array)==0:
            return []
        i, j = 0, len(array)-1
        while i<=j:
            if array[i]+array[j] == tsum:
                return [array[i], array[j]]
            elif array[i]+array[j] > tsum:
                j -= 1
            elif array[i]+array[j] < tsum:
                i += 1
        return []

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;

public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> res = new ArrayList<>();
        PriorityQueue<String> queue = new PriorityQueue<>(new MyComparator());
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if (array[i] + array[j] == sum) {
                    String string = array[i] + " " + array[j];
                    queue.add(string);
                }
            }
        }
        if (queue.isEmpty()) {
            return new ArrayList<Integer>();
        }
        String resString = queue.poll();
        int former = Integer.valueOf(resString.split(" ")[0]);
        int latter = Integer.valueOf(resString.split(" ")[1]);
        res.add(former);
        res.add(latter);
        return res;
    }
    
    // 比较器
    public static class MyComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            int former = Integer.valueOf(a.split(" ")[0]) * Integer.valueOf(a.split(" ")[1]);
            int latter = Integer.valueOf(b.split(" ")[0]) * Integer.valueOf(b.split(" ")[1]);
            return former - latter;
        }
    }
}

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, S):
        # write code here
        lis=list(array)
        l=[]
        if not lis:
            return []
        m=lis[-1]**2#用来记录当前最大乘积
        for i in lis:
            for j in lis[::-1]:
                if i+j==S:
                    m=min(m,i*j)
                    if m==i*j:
                        l=[]
                        l.append(min(i,j))
                        l.append(max(i,j))
                    break
        return l 

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        long mult = Long.MAX_VALUE;
        int low = 0,high = array.length - 1;
        int first = 0,second = 0;
        while(low < high){
            if(array[low] + array[high] == sum){
                long t = (long)array[low] * (long)array[high];
                if(mult > t){
                    mult = t;
                    first = array[low];
                    second = array[high];
                }
                low++;
                high--;
            }
            else if(array[low] + array[high] > sum) high--;
            else low++;
        }
        ArrayList<Integer> r = new ArrayList<Integer>();
        if(first == second) return r;
        r.add(first);
        r.add(second);
        return r;
    }
}
//相距越远，乘积越小，直接从首尾开找
// x+y = s, x*y = x(s-x) = -x^2+sx = -(x-s/2)^2 + s^2/4.
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int low = 0,high = array.length - 1;
        ArrayList<Integer> r = new ArrayList<Integer>();
        while(low < high){
            if(array[low] + array[high] == sum){
                r.add(array[low]);
                r.add(array[high]);
                break;
            }
            else if(array[low] + array[high] > sum) high--;
            else low++;
        }
        return r;
    }
}

import java.util.ArrayList;

/**
 * 题目描述
 * 输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，
 * 如果有多对数字的和等于S，输出两个数的乘积最小的。
 * 输出描述:
 * 对应每个测试案例，输出两个数，小的先输出。
 *
 * @author shijiacheng
 */
public class FindNumbersWithSumSolution {
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Integer> result = new ArrayList<>();
        ArrayList<ArrayList<Integer>> totalResult = new ArrayList<>();
        if (array.length < 1) {
            return result;
        }
        int small = 0;
        int big = array.length - 1;
        while (big > small) {
            int curSum = array[small] + array[big];
            if (curSum == sum) {
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(array[small]);
                temp.add(array[big]);
                totalResult.add(temp);
                big--;
            } else if (curSum > sum) {
                big--;
            } else {
                small++;
            }
        }

        if (totalResult.size() > 0) {
            int number = Integer.MAX_VALUE;
            for (int i = 0; i < totalResult.size(); i++) {
                int temp = totalResult.get(i).get(0) * totalResult.get(i).get(1);
                if (number > temp) {
                    number = temp;
                    result.clear();
                    result.add(totalResult.get(i).get(0));
                    result.add(totalResult.get(i).get(1));
                }
            }
        }

        return result;
    }
}