经典题目系列-N数之和问题

二数之和-题目描述

输入一个数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。

如果有多对数字的和等于s，输出任意一对即可。

你可以认为每组输入中都至少含有一组满足条件的输出。

样例

输入：[1,2,3,4] , sum=7

输出：[3,4]

二数之和-总体思路

（1）Hash $O(n)$

（2）排序后，双指针 $O(nlgn)$

二数之和-代码实现

class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i) {
            hash[nums[i]] = i;
        }
        vector<int> res(2, 0);
        for (int i = 0; i < nums.size(); ++i) {
            auto r = hash.find(target - nums[i]);
            if (r != hash.end()) {
                res[0] = nums[i];
                res[1] = nums[r->second];
            }
        }
        return res;
    }
};

连续序列和-题目描述

输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。

例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。

样例
输入：15

输出：[[1,2,3,4,5],[4,5,6],[7,8]]

连续序列和-总体思路

首先最容易想到的思路：
（1）用两个下标i,j分别指向序列的开始结束位置
（2）用等差序列求和公式计算和是否等于S，如果等于S，则记录答案

class Solution {
public:
        vector<vector<int> > findContinuousSequence(int t) {
        int i = 1, j = 1;
        int sum = 0;
        for (int i = 1; i < t; i++) { //结束位置
            for (j = 1; j < i; j++) { //开始位置
                if (S[i, j] == t) {
                    //add to result
                }
            }
        }
        return res; 
    }
};

以上时间复杂度为$O(n^2)$

这里有一个经验：
如果你的算法需要从$O(n^2)$优化到$O(n)$, 一般情况下我们可以考虑三种常用手段：双指针、单调队列、单调栈。这三种常用手段都充分利用了这个基本事实：内层循环变量j伴随外层循环变量i单调变化，此处单调变化指的是：i往前走一步，j也只会增加而不会回退。

根据上面的经验，我们重新审视变量j与变量i的关系发现，确实有单调性，所以我们可以通过双指针来优化。

还有一点特别重要，那就是代码模版，我们需要非常熟悉各种常见的算法模版，以下为双指针算法的代码模版：

void two_pointer() {
    int i, j;
    while (i < n) {
        //新来一个元素
        while (j < n && check(j)) j++; 
    }
}

连续序列和-代码实现

class Solution {
public:
        vector<vector<int> > findContinuousSequence(int t) {
        int i = 1, j = 1;
        int sum = 0;
        vector<vector<int> > res; //[i, j-1]的和，明确sum的含义
        while (j < t) {
            if (sum > t) {
                while (sum > t) {
                    sum -= i;
                    i++;
                }
            }
            else {
                sum += j;
                j++;
            }
            
            if (sum == t) {
                int p = i;
                vector<int> one;
                while (p <= j - 1) {
                    one.push_back(p++);
                }
                res.push_back(one);
            }
        }  

        return res; 
    }
};