寻找和为定值的多个数

时间:2021-05-22 20:32:07

问题:
1. 找出一个序列中和为sum的两个数
2. 找出一个序列中和为sum的多个数(不限个数)
3. 找出一个序列中和为sum的4个数

解析:

1. 找出一个序列中和为sum的两个数

  • 将序列排序
  • 用左右2个指针指向序列的头部和尾部
  • 如果当前2个指针指向数的当前和等于sum,则这两个数是一个结果;如果当前和小于sum,说明当前和应该大一点,则将左指针右移 1 位;如果当前和大于sum,说明当前和应该小一点,则将右指针左移 1 位

2. 找出一个序列中和为sum的多个数(不限个数)

0-1 背包问题,考虑是否取第 n 个数可以转化为只和前 n-1 个数有关的问题

  • 取第 n 个数,则问题转为“对 n - 1 个数中,找出和为 sum - input[n-1]的数”(第 n 个数的下标是 n-1):sumOfkNumber(sum - input[n-1], n - 1);
  • 不取第 n 个数,则问题转为“对 n - 1 个数中,找出和为 sum的数”:sumOfkNumber(sum, n - 1);

3. 找出一个序列中和为sum的4个数

针对找出和为sum的多个数,控制加入数的数量,只有恰好有 4 个数,才看做一个结果。

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
using namespace std;
class Solution {
public:
    // 两个数
    void PrintTwoNumWithSum(vector<int> input, int sum)
    {
        if (input.size() < 1 || sum < 0)
            return;
        int i = 0;
        int j = input.size() - 1;
        while (i < j) {
            int curSum = input[i] + input[j];
            if (curSum == sum) {
                cout << input[i] << " " << input[j] << endl;
                ++i;
            } else if (curSum < sum) {
                ++i;
            }   else {
                --j;
            }
        }
    }
    // 多个数
    void PrintNNumWithSum(vector<int> &input, int sum) {
        if (input.size() < 1 || sum < 0)
            return;
        vector<int> result;
        PrintNNumWithSumHelper(input, input.size()-1, sum, result);
    }
    // 四个数
    void Print4NumsWithSum(vector<int> &input, int sum, int m) {
        if (input.size() < 1 || sum < 0)
            return;
        vector<int> result;
        Print4NumWithSumHelper(input, input.size() - 1, sum, m, result);
    }
private:
    // 多个数
    void PrintNNumWithSumHelper(vector<int> &input, int n, int sum, vector<int> &result) {
        if (n < 0 || sum < 0)
            return;
        if (sum == input[n]) {
            cout << input[n] << " ";
            if (result.size() > 0) {
                for (int i = result.size() - 1; i >= 0; i--) {
                    cout << result[i] << " ";
                }
            }
            cout << endl;
        }
        result.push_back(input[n]);
        PrintNNumWithSumHelper(input, n - 1, sum - input[n], result);
        result.pop_back();
        PrintNNumWithSumHelper(input, n - 1, sum, result);
    }
    // 四个数
    void Print4NumWithSumHelper(vector<int> &input, int n, int sum, int m, vector<int> &result) {
        if (n < 0 || sum < 0 || result.size() == m)
            return;
        if (result.size() == m-1 && sum == input[n]) {
            cout << input[n] << " ";
            if (result.size() > 0) {
                for (int i = result.size() - 1; i >= 0; i--) {
                    cout << result[i] << " ";
                }
            }
            cout << endl;
        }
        result.push_back(input[n]);
        Print4NumWithSumHelper(input, n - 1, sum - input[n], m, result);
        result.pop_back();
        Print4NumWithSumHelper(input, n - 1, sum, m, result);
    }
};

int main()
{
    vector<int> input;
    for (int i = 0; i < 50; i++) {
        input.push_back(i + 1);
    }
    sort(input.begin(), input.end());
    Solution sol;
    int sum = 20;
    cout << "======打印和为 " << sum <<" 的两个数=======" << endl;
    sol.PrintTwoNumWithSum(input, sum);
    cout << "======打印和为 " << sum << " 的数=======" << endl;
    sol.PrintNNumWithSum(input, sum);
    cout << "======打印和为 " << sum << " 的4个数=======" << endl;
    sol.Print4NumsWithSum(input, sum, 4);
}

参考资料:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.03.md