57.和为S的两个数字.md

57.和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

返回值描述:

对应每个测试案例，输出两个数，小的先输出。

输入

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

返回值

[4,11]

思路 & 解答

暴力遍历

直接遍历每两个数，查看其和是否符合等于sum,再计算其乘积，是否小于之前的乘积，如果小于，则更新。

import java.util.ArrayList;
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Integer> results = new ArrayList<>();
        long mutip = 999999999;
        if (array != null && array.length > 2) {
            for (int i = 0; i < array.length - 1; i++) {
                for (int j = i + 1; j < array.length; j++) {
                    if (array[i] + array[j] == sum && array[i] * array[j] < mutip) {
                        results.clear();
                        results.add(array[i]);
                        results.add(array[j]);
                        mutip = array[i] * array[j];
                    } else if (array[i] + array[j] > sum) {
                        break;
                    }
                }
            }
        }
        return results;
    }

C++ 代码实现如下：

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array, int sum) {
        vector<int> results;
        long mutip = 999999999;
        if (array.size() > 2) {
            for (int i = 0; i < array.size() - 1; i++) {
                for (int j = i + 1; j < array.size(); j++) {
                    if (array[i] + array[j] == sum && array[i] * array[j] < mutip) {
                        results.clear();
                        results.push_back(array[i]);
                        results.push_back(array[j]);
                        mutip = array[i] * array[j];
                    } else if (array[i] + array[j] > sum) {
                        break;
                    }
                }
            }
        }
        return results;
    }
};

使用 HashSet

针对每一个数字 a，都查看hashset中是否存在sum-a，同时把该数字添加到set中。如果存在则计算其乘积，更新乘积最小值。

    public ArrayList<Integer> FindNumbersWithSum1(int[] array, int sum) {
        ArrayList<Integer> results = new ArrayList<>();
        long mutip = 999999999;
        HashSet<Integer> set = new HashSet<>();
        if (array != null && array.length > 2) {
            for (int i = 0; i < array.length; i++) {
                if (set.contains(sum - array[i]) && array[i]*(sum - array[i]) < mutip) {
                    results.clear();
                    results.add(sum-array[i]);
                    results.add(array[i]);
                    mutip = array[i] * (sum - array[i]);
                }
                set.add(array[i]);
            }
        }
        return results;
    }

C++ 代码如下：

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array, int sum) {
        vector<int> results;
        long mutip = 999999999;
        set<int> set;
        if (array.size() > 2) {
            for (int i = 0; i < array.size(); i++) {
                if (set.count(sum - array[i])>0 && array[i]*(sum - array[i]) < mutip) {
                    results.clear();
                    results.push_back(sum-array[i]);
                    results.push_back(array[i]);
                    mutip = array[i] * (sum - array[i]);
                }
                set.insert(array[i]);
            }
        }
        return results;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

双指针法

前面讲解的是暴力破解和hash法，这里讲解的是双指针法。

由于数组nums[]是有序的，也就是第一个数字是最小的，第二个数字是最大的，那么我们使用一个指针i指向数组第一个元素，一个指针j指向数组最后一个元素。 i指针往右边移动，j指针往左边移动,直到两者相撞（相等）。

• 如果nums[i]+nums[j]==sum,那么说明这个是可能存在的解，需要计算两者的乘积，如果比保存的乘积还小，则更新结果。同时左边指针i往右边移动一位，右边指针j往左边移动一位。
• 如果nums[i] + nums[j] > sum,则说明和太大了，比sum还要大，则右边的指针j需要左移一步，即是j--。
• 如果nums[i] + nums[j] < sum,则说明和太小了，比sum还要小，则左边的指针i需要左移一步，即是i++。

    public ArrayList<Integer> FindNumbersWithSum2(int[] array, int sum) {
        ArrayList<Integer> results = new ArrayList<>();
        long mutip = 999999999;
        if (array != null && array.length > 2) {
           int left = 0,right = array.length-1;
           while(left<right){
               if(array[left]+array[right]==sum){
                   if(array[left]*array[right]<mutip){
                       mutip = array[left]*array[right];
                       results.clear();
                       results.add(array[left]);
                       results.add(array[right]);
                   }
                   left++;
                   right--;
               }else if(array[left]+array[right]>sum){
                   right--;
               }else{
                   left++;
               }
           }
        }
        return results;
    }

C++ 代码实现如下：

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array, int sum) {
        vector<int> results;
        long mutip = 999999999;
        if (array.size() > 2) {
            int left = 0, right = array.size() - 1;
            while (left < right) {
                if (array[left] + array[right] == sum) {
                    if (array[left] * array[right] < mutip) {
                        mutip = array[left] * array[right];
                        results.clear();
                        results.push_back(array[left]);
                        results.push_back(array[right]);
                    }
                    left++;
                    right--;
                } else if (array[left] + array[right] > sum) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return results;
    }
};

由于左右指针加起来最多是将数组遍历一遍，所以时间复杂度为O(n)。