N数之和问题：给定一个对于所有自变量$x_1, x_2, \cdots, x_n$都在一个有限的整数区间中，且严格单调递增的函数$f(x_1, x_2, \cdots, x_n)$。如何找到该函数的零点？

为了解决N数之和问题，我们首先考虑两数之和问题，我们从一个无任何附加信息的两和之和问题开始，通过不断添加新的信息，利用新的信息，来降低算法的复杂度。

问题一：
给定一个关于在相同有限区间$S$内的整数变量$x$和$y$的函数$f(x, y)$。找到$f(x,y)$的零点。
通过暴力搜索所有可能的状态空间找到答案。搜索空间的大小即$|S|^2$。通过遍历所有的$(x, y)$，找到所有使得$f(x, y)=0$的解。

  y 0   ...   N
x  +-----------+
0  |X|X|X|X|X|X|
   +-----------+
   |X|X|X|X|X|X|
.  +-----------+
.  |X|X|X|X|X|X|
.  +-----------+
   |X|X|X|X|X|X|
   +-----------+
   |X|X|X|X|X|X|
   +-----------+
N  |X|X|X|X|X|X|
   +-----------+

问题二：
给定一个关于在相同有限区间$S$内的整数变量$x$和$y$的函数$f(x, y)$。对于方程$f(x, y) = 0$，有隐函数$y = h(x)$。找到$f(x,y)$的零点。

由于函数$y = h(x)$存在，在给定$x$的时候，我们可以找到对应的$y$。因此当我们在遍历$x$的所有可能取值时，可以用$h(x)$计算出其对应的$y$，并放在一个hashset中。每次到下一个$s$的可能取值时，因为$x$和$y$的取值范围是完全相同的，所以可以先在hashset中查看是否有该值，如果有，则找到了一个解。

或者当函数$y = h(x)$计算代价不大时，我们不必在hashset中记录$x$对应的$y$，而是直接记录$x$。

x 0   ...   N
 +-----------+
 |X|X|X|X|X|X|
 ++-+-+-+-+-++
  ^ ^ ^ ^ ^ ^
  | | | | | | y = h(x)
  v v v v v v
 +++++++++++++
 | | | | | | |
 +-+-+-+-+-+-+

问题三：
给定一个关于在相同有限区间$S$内的整数变量$x$和$y$，且严格单调递增的函数$f(x, y)$，找到$f(x,y)$的零点。

考虑函数的单调性：
因为$f(x, y)$严格单调递增，所以我们有

$\forall t > x, f(t, y) > f(x, y)$
$\forall t < y, f(x, t) < f(x, y)$

为了利用上述两条性质，我们将有限区间$S$所有可能的取值进行排序。之后让$x$等于区间中的最小值$i$。让$y$等于区间中的最大值$j$。判断$f(i, j)$和0的大小关系：

如果$f(i, j) < 0$，则$\forall t < j, f(i, t) < f(i, j) < 0$。因此当$x = i$时，$\forall y \in S, f(i, y) < 0$。我们可以在搜索空间中划除$i$对应的这一行。
如果$f(i, j) > 0$，则$\forall t > i, f(t, j) > f(i, j) > 0$。因此当$y = j$时，$\forall x \in S, f(x, j) > 0$。我们可以在搜索空间中划去$j$对应的这一列。
如果$f(i, j) = 0$，我们找到了一个结果。但根据严格单调递增性，我们不会在$i$,$j$所在的行列再找到任何其他一对数字使得$f(x, y) = 0$。我们可以在搜索空间划去$i$对应的这一行和$j$对应的这一列。

之后我们得到了一个新的搜索空间。我们继续从这个搜索空间的右上角（即$i$取最小值，$j$取最大值）重复上面的算法，直到搜索空间为空。

                start                 start
  y i   ...   j   +     y i   ...   j   +
x  +-----------+  |   x  +-----------+  |
i  |X|X|X|X|X|X+<-+   i  | | | | | |X+<-+
   +-----------+         +-----------+
   | | | | | | |         | | | | | |X|
.  +-----------+      .  +-----------+
.  | | | | | | |      .  | | | | | |X|
.  +-----------+      .  +-----------+
   | | | | | | |         | | | | | |X|
   +-----------+         +-----------+
   | | | | | | |         | | | | | |X|
   +-----------+         +-----------+
j  | | | | | | |      j  | | | | | |X|
   +-----------+         +-----------+

问题三的一个典型例题，未给出函数表达式，仅强调了单调性：LC1237 找出给定方程的正整数解

给定函数严格单调递增
$f(x, y) < f(x + 1, y)$
$f(x, y) < f(x, y + 1)$
在$0 \leq x \leq 1000$ 和 $0 \leq y \leq 1000$的条件下，找到使得$f(x, y) - z = 0$的所有可能的解。
思路：
搜索空间为$\{(x,y)| 0 \leq x \leq 1000, 0 \leq y \leq 1000, x \in \mathbb{Z}, y \in \mathbb{Z}\}$，如下图所示。

                     (a, b)
                      ^
                      |
    j 0   ...  1000   |    j 0   ...  1000        j 0   ...  1000
  i  +-+-+-+-+---+    |  i  +-+-+-+-+---+       i  +-----------+
  0  | | | | | |S+----+  0  | | | | | |X|       0  |X|X|X|X|X|X|
     +-----------+          +-----------+          +-----------+
     | | | | | | |          | | | | | |X|          | | | | | | |
     +-----------+          +-----------+          +-----------+
  .  | | | | | | |       .  | | | | | |X|       .  | | | | | | |
  .  +-----------+       .  +-----------+       .  +-----------+
  .  | | | | | | |       .  | | | | | |X|       .  | | | | | | |
     +-----------+          +-----------+          +-----------+
     | | | | | | |          | | | | | |X|          | | | | | | |
     +-----------+          +-----------+          +-----------+
1000 | | | | | | |     1000 | | | | | |X|     1000 | | | | | | |
     +-+---+-+-+-+          +-+-+---+---+          +-+-+-+---+-+
         |                        ^                        ^
         |    f(a, b) - z > 0     |                        |
         +------------------------+                        |
         |                                                 |
         |    f(a, b) - z < 0                              |
         +-------------------------------------------------+

根据函数严格单调递增的性质，我们知道
$f(a, b) - z < 0$，且$b$一定时，$\Rightarrow \forall x \in [a, 1000], f(x, b) < 0$
$f(a, b) - z > 0$，且$a$一定时，$\Rightarrow \forall x \in [b, 1000], f(a, x) > 0$
$f(a, b) - z = 0$，当$a$一定时，$\Rightarrow \forall x \in (b, 1000], f(a, x) \neq 0$
$f(a, b) - z = 0$，当$b$一定时，$\Rightarrow \forall x \in (a, 1000], f(x, b) \neq 0$
从右上角$(0, 1000)$的位置开始搜索。根据$f(a, b) - z$和$0$的大小关系，可以划去一行和（或）者一列。

即当$f(a, b) - z > 0$时，我们可以划去当前$a$在搜索空间中对应的这一行数字，因为函数单调递增，增加$a$只会使得$f(a, b) - z$变得更大。
当$f(a, b) - z < 0$时，我们可以划去$b$在搜索空间中对应的这一列数字。
当$f(a, b) - z = 0$时，我们同时划去$(a, b)$在搜索空间对应这一行和这一列。

code

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        auto res = vector<vector<int>>{};
        auto a = 1;
        auto b = 1000;
        while(a <= 1000 && b >= 1)
        {
            if(customfunction.f(a, b) - z < 0)
            {
                ++a;
            }
            else if(customfunction.f(a, b) - z > 0)
            {
                --b;
            } 
            else
            {
                res.emplace_back<initializer_list<int>>({a, b});
                ++a;
                --b;
            }
        }

        return res;
    }
};

问题4：

给定一个关于在相同有限区间$S$内的整数变量$x$和$y$，且严格单调递增的函数$f(x, y)$，找到$f(x,y) < 0$的所有解。

当我们找到一个点使得$f(a, b) < 0$时，因为单调性，所有在该点同一列，且该点上方的点$(t, b), t < a$都有$f(t, b) < 0$。所有在该点同一行，且在该点左侧的点$(a, t), t < b$都有$f(a, t) < 0$
同理，当我们找到一个点使得$f(a, b) \geq 0$时，其下方和右侧所有的点$(m, n)$也都满足$f(m, n) \geq 0$。

          ^
          |
  j 0     |   N      j 0         N
i  +-+-+--|--+-+   i  +-+-+-+-+-+-+
0  | | | ||| | |   0  | | | | | | |
   +------|----+      +-----------+
   | | | ||| | |      | | | | | | |
   +------|----+      +-----------+
<---------X| | |      | | | |X--------->
   +-----------+      +------|----+
   | | | | | | |      | | | ||| | |
   +-----------+      +------|----+
   | | | | | | |      | | | ||| | |
   +-----------+      +------|----+
N  | | | | | | |   N  | | | ||| | |
   +-+-+-+-+-+-+      +-+-+--|--+-+
                             |
                             |
                             v

我们仍然选择从右上角（或者左下角）开始进行搜索。我们不断地移动$x$，初始化$y$为0。
我们通过判断$f(x, y) \geq 0$来找到这一列的第一个有效解的$y$。我们记录下这个$y$的位置，在下一次循环开始后，因为$x$增加，$y$必不可能减少。我们无需从$N$开始重新搜索，只需要从上一次的$y$位置开始搜索，找到第一个有效位置即可。

int cnt = 0;
int y   = N;
for(int x = 0; x <= N; ++x)
{
    // update y to its first valid position in this row
    while(f(x, y) >= 0)
    {
        --y;
    }
    cnt += y;
}

  j 0         N
i  +-----------+
0  |O|O|O|O|X|X|<--- 第一次在 --y 两次后找到了第一个可行解，其左侧就都是可行解
   +-----------+
   |O|O|O|X| | |<--- ++j后，第二次接着第一次结束的位置开始搜索。
   +-----------+
   |O|O|O| | | |
   +-----------+
N  |O|X|X| | | |
   +-+-+-+-+-+-+

问题4的典型例题为LC719 找出第 k 小的距离对

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对$(A, B)$的距离被定义为 A 和 B 之间的绝对差值。

我们可以用二分搜索找到第k个最小距离。注意到该整数数组中距离的最大值为数组的最大值减去数组的最小值。最小值可能为0。为们在距离上进行二分搜索：

设$g(d)$为在该数组上，小于$d$的距离对的数目。
维护二分搜索区间，使得
- 对于[begin, first)所在区间的任意值$t$，$g(t) < k$
- 对于[last, end)所在区间的任意值$t$，$g(t) >= k$
- first < last
  最后first == last所停在的位置即为结果。

该题目的关键点在于函数$g$的实现。注意到如果我们将该数组排序，并总是用较大的数减去较小的数，就不用考虑绝对值的问题。对于一对点$(x, y)$，他们之间的距离与$t$的差$f(x, y)$是关于x递减，关于y递增的函数。参照问题四，如果一点$f(x, y) < 0$，那么他左侧和他下方的点都满足$f(x, y) < 0$。如果一点$f(x, y) > 0$，那么他上方和他右侧的点也都满足$f(x, y) > 0$。我们考虑从左上角开始搜索。移动j并不断通过$f(x,y)$和0的关系判断移动i。这里和问题4不同的地方在于，数组中的每个数只能选取一次，且距离函数是对称的。有一半的搜索空间是无效的，因此我们每次累加cnt += j - i个。

auto dist_cnt(vector<int>& nums, int k) -> size_t
{
    auto cnt = 0;
    auto i = 0;
    for(auto j = i + 1; j < nums.size(); ++j)
    {
        while(nums[j] - nums[i] > k)
        {
            ++i;
        }
        cnt += j - i;
    }
    return cnt;
}

code

auto dist_cnt(vector<int>& nums, int k) -> size_t
{
    auto cnt = 0;
    auto i = 0;
    for(auto j = i + 1; j < nums.size(); ++j)
    {
        while(nums[j] - nums[i] > k)
        {
            ++i;
        }
        cnt += j - i;
    }
    return cnt;
}

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        auto first = 0;
        auto last  = nums.back() - nums.front();
        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            //cout<<first<<" "<<mid<<" "<<last<<" "<<dist_cnt(nums, mid);
            if(dist_cnt(nums, mid) < k)
            {
                first = mid + 1;
            }
            else
            {
                last = mid;
            }
        }

        return first;
    }
};

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

改变叙述方式，该题目即对于属于整数数组中的$x$和$y$，找到函数$f(x, y) = x + y - t$的一个零点。

思路一：

对于$y$，我们可以求得其对应的$x$为$x = t - y$。因此我们可以使用问题二的思路，通过一个hashmap来解决。
- 从左到右遍历数组，在遍历过程中，对于每个元素a，查询unordered_map中是否有target - a。如果有，就返回结果。
- 将(a, a_i)放入unordered_map中。
- 即使遍历一次，仍然考虑到了所有的(i, j)的可能性。

code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        auto m = unordered_map<int, int>{};
        for(auto i = size_t{}; i < nums.size(); ++i)
        {
            auto x = nums[i];
            if(auto it = m.find(target - x);
            it != m.end())
            {
                return {it->second, static_cast<int>(i)};
            }
            m[x] = i;
        }
        return {-1, -1};
    }
};

我们可以发现，函数表达式$f(x, y) = x + y - t$对于$x$和$y$都是严格单调递增的。因此我们可以采用问题三的思路。先将数组排序，之后从$x$取最小值，$y$取最大值的位置开始搜索。即双指针法。然而LC1 两数之和这个题目，要求返回原来的元素下标。因此我们必须使用一个map 来建立有序的数值-下标对应关系。或者使用一个unordered_map来记录对应关系后再进行排序。这两种方法都不如思路一简单，且效率较低。最适合利用单调性的是输入的数组已经排序好了的167 两数之和 II - 输入有序数组

当数组有序时
我们设置两个指针，一个位于数组第一个元素front，一个位于数组最后一个元素back。

保证front < back
- 如果target < *front + *back，说明*first小了，将first往前移动一位。
- 如果target > *front + *back，说明*back大了，将back往后移动一位。
- 如果target == *front + *back，得到结果返回。

  j 0 1 2 3 4 5      j 0 1 2 3 4 5      j 0 1 2 3 4 5
i  +-+-+-+-+-+-+   i  +-+-+-+-+-+-+   i  +-+-+-+-+-+-+
0  |O| | | | |S|   0  |O|X|X|X|X|X|   0  |O| | | | |X|
   +-----------+      +-----------+      +-----------+
1  |O|O| | | | |   1  |O|O| | | | |   1  |O|O| | | |X|
   +-----------+      +-----------+      +-----------+
2  |O|O|O| | | |   2  |O|O|O| | | |   2  |O|O|O| | |X|
   +-----------+      +-----------+      +-----------+
3  |O|O|O|O| | |   3  |O|O|O|O| | |   3  |O|O|O|O| |X|
   +-----------+      +-----------+      +-----------+
4  |O|O|O|O|O| |   4  |O|O|O|O|O| |   4  |O|O|O|O|O|X|
   +-----------+      +-----------+      +-----------+
5  |O|O|O|O|O|O|   5  |O|O|O|O|O|O|   5  |O|O|O|O|O|O|
   +-+---+-+-+-+      +-+-+---+-+-+      +-+-+---+-+-+
       |    (0, 5) < target ^                  ^
       +--------------------+                  |
       |    (0, 5) > target                    |
       +------------+--------------------------+

算法开始时，我们搜索位置$(0,5)$。因为数组是有序的，所以第一行中位置$(0,0)$到$(0,4)$的值都要比$(0,5)$小。最后一列中$(1,5)$到$(5,5)$都要比$(0,5)$大。

如果我们发现target $ > (0,5)$，那么第一行中所有的值因为必然小于$(0, 5)$，也就小于target，就不必再搜索了。因此我们向前移动i
同理，如果$(0,5)$比target大，那么最后一列的内容就不必搜索了。因此我们向前移动j
之后重复上述过程，即可找到target。

解释：一张图告诉你 O(n) 的双指针解法的本质原理（C++/Java）- nettee, Leetcode

code

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        auto f = numbers.begin();
        auto b = numbers.end() - 1;

        while(f < b)
        {
            if(*f + *b < target)
            {
                ++f;
            }
            else if(*f + *b > target)
            {
                --b;
            }
            else
            {
                return
                {
                    static_cast<int>(f - numbers.begin() + 1),
                    static_cast<int>(b - numbers.begin() + 1)
                };
            }
        }

        return {-1, -1};
    }
};

接下来是一个在动态的数组上寻找两数之和的问题：170. 两数之和 III - 数据结构设计

不同于之前的两数之和问题，该题目中可能出现重复的数字，也可能出现多个可能解。

选择一：排序数组。每次add操作必须要保证数组有序，因此会有$O(N)$的时间复杂度。find操作可以使用双指针。
选择二：排序链表。add不能进行二分查找，$O(N)$的时间复杂度。find可以使用双指针。内存局部性差。
选择三：hashmap。add期望$O(1)$，查找$O(N)$。
选择四：数组不排序。每次find时再排序。之后双指针查找。

可以看到，如果想要利用单调性来解决该问题，就必须得维持数组有序，代价较高。在已知表达式的情况下，显然是hashmap法要更简洁高效。

注意：因为存在重复元素，我们需要统计元素的个数。当hashmap中存在一个元素a，2 * a和所查询元素相等时，如果a只出现1次，要返回false。

3 - code

class TwoSum {
private:
    unordered_map<int, size_t> m_storage;
public:
    /** Initialize your data structure here. */
    TwoSum() {}
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        ++m_storage[number];
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        for(const auto& p : m_storage)
        {
            if((value - p.first == p.first && m_storage[p.first] > 1)
            || (value - p.first != p.first && m_storage.count(value - p.first)))
            {
                return true;
            }
        }
        return false;
    }
};

在BST上的两数之和问题，可以尝试设计BST的迭代器来解决。
653. 两数之和 IV - 输入 BST

思路一：双指针。为了实现在BST上的双指针，我们需要一个BST的正向迭代器，和一个反向迭代器。迭代其的实现见173. 二叉搜索树迭代器

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

template<TreeNode* TreeNode::* left, TreeNode* TreeNode::* right>
class BSTIterator {
private:
    stack<TreeNode*> m_stack;
    TreeNode* m_root;
public:
    BSTIterator(TreeNode* root)
    :m_stack{}
    ,m_root{root}
    {}
    
    /** @return the next smallest number */
    int next() {
        return inorder()->val;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return m_root || !m_stack.empty();
    }

    auto inorder() -> TreeNode*
    {
        while(m_root)
        {
            m_stack.push(m_root);
            m_root = m_root->*left;
        }

        if(m_stack.empty())
        {
            return m_root;
        }

        m_root = m_stack.top();
        m_stack.pop();

        auto res = m_root;
        m_root = m_root->*right;

        return res;
    }
};

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        auto it  = BSTIterator<&TreeNode::left, &TreeNode::right>{root};
        auto rit = BSTIterator<&TreeNode::right, &TreeNode::left>{root};

        auto l = it.next();
        auto r = rit.next();

        while(l != r)
        {
            if(l + r < k)
            {
                l = it.next();
            }
            else if(l + r > k)
            {
                r = rit.next();
            }
            else
            {
                return true;
            }
        }

        return false;
    }
};

思路二：花费很大经历去写BST的迭代器比较麻烦。直接中序便利整个BST，将结果放入一个数组里再用双指针。
思路三：无视BST的有序性质，直接采用LC1 两数之和的unordered_map来做。

LC1099 小于 K 的两数之和

按照问题二的思路：
我们不能再使用无序的hashset来记录已经遍历的结果。因为对于我们当前的数$x$，我们要找到以前遍历过的数字中，小于$K - x$且最最大的。因此我们需要使用一个有序容器set来记录之前遍历的数字。我们以greater<int>作为set的比较函数，这样我们在使用upper_bound时，就可以找到首个小于$K - x$的元素了。

code

class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        auto s = set<int, greater<int>>{};
        auto res = INT_MIN;
        for(auto i = A.begin(); i < A.end(); ++i)
        {
            auto j = s.upper_bound(K - *i);
            if(j != s.end())
            {
                res = max(res, *i + *j);
            }
            s.insert(*i);
        }
        return res == INT_MIN ? -1 : res;
    }
};

按照问题三的思路，我们将数组排序后利用单调性：

当*l + *r >= K时，因为数组有序，在[l, r)之间的任意的位置p都会使得*p + *r >= K，因此--r。当*l + *r < K时，记录下此时的*l + *r，[begin, l)之间任意的位置p，都会使得*p + *r < *l + *r，绝不比*l + *r更接近K。因此++l。

code

class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        auto l = A.begin();
        auto r = A.end() - 1;
        auto res = INT_MIN;
        while(l < r)
        {
            if(!(*l + *r < K))
            {
                --r;
            }
            else
            {
                res = max(res, *l + *r);
                ++l;
            }
        }

        return res == INT_MIN ? -1 : res;
    }
};

LC560 和为K的子数组

利用数组的前缀和，将问题转化为两数之和问题：

寻找两个前缀和a，b，使得b - a == k或寻找一个数字a，使得a == k
因为有重复元素，因此按照[LC1 两数之和]的去重hashmap法来做。

code

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        auto mp = unordered_map<int, int>{};
        auto sum = 0;
        auto cnt = 0;
        for(auto n : nums)
        {
            sum += n;
            if(auto it = mp.find(sum - k);
            it != mp.end())
            {
                cnt += it->second;
            }
            if(sum == k)
            {
                ++cnt;
            }
            ++mp[sum];
        }
        return cnt;
    }
};

LC1171 从链表中删去总和为零的连续节点

使用前缀和。因为要求总和为零，所以表达式已知。使用一个hashmap从前向后遍历。要求直到不存在这样的序列为止。因此在遍历过程中递归。

code

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {

        auto dummy = ListNode{0};
        auto np = &dummy;
        np->next = head;

        auto mp = unordered_map<int, ListNode*>{};
        auto sum = 0;
        while(np)
        {
            sum += np->val;
            if(auto it = mp.find(sum);
            it != mp.end())
            {
                it->second->next = np->next;
                dummy.next = removeZeroSumSublists(dummy.next);
                break;
            }
            mp[sum] = np;
            np = np->next;
        }
        return dummy.next;
    }
};

LC327 区间和的个数

类似LC560 和为K的子数组，利用前缀和，将问题转化为两数之和。

因为不是寻找相等的，而是寻找在一个区间内的，我们使用multiset来代替hashmap
遍历数组，计算每个位置对应的前缀和
- 如果该前缀和sum本身位于[l, u]之间，那么该位置到数组头一个元素构成的区间满足条件，++cnt（也可以在multiset中放置一个guard元素0来省略这一步）
- 之后在multiset中寻找能够使得sum - b满足位于[l, u]之间的b。b应该满足sum - b >= l && sum - b <= u + 1。即寻找lower_bound(sum - l + 1)到lower_bound(sum - u)之间元素的个数。

code

class Solution {
public:
    int countRangeSum(vector<int>& nums, int64_t l, int64_t u) {
        auto sum = int64_t{};
        auto s = multiset<int64_t>{};
        auto cnt = 0;
        for(auto n : nums)
        {
            sum += n;
            if(sum >= l && sum <= u)
            {
                ++cnt;
            }
            auto li = s.lower_bound(sum - u);
            auto ui = s.lower_bound(sum - l + 1);
            cnt += distance(li, ui);
            s.insert(sum);         
        }
        return cnt;
    }
};

class Solution {
public:
    int countRangeSum(vector<int>& nums, int64_t l, int64_t u) {
        auto sum = int64_t{};
        auto s = multiset<int64_t>{};
        s.insert(0);
        auto cnt = 0;
        for(auto n : nums)
        {
            sum += n;
            auto li = s.lower_bound(sum - u);
            auto ui = s.lower_bound(sum - l + 1);
            cnt += distance(li, ui);
            s.insert(sum);         
        }
        return cnt;
    }
};

N数之和问题

LC15 三数之和

固定a的位置，移动b和c来当作两数之和来做。

找到所有可能的三元组：每当找到一个可能的三元组时，因为数组有序，我们可以确定地认为：
- 当b一定时，改变c到(b, c)之间的任何一个元素t，都不会有a + b + t == 0，因此++b
- 同理，当c一定时，改变b到(b, c)之间的任何一个元素，都不会有a + b + t == 0，因此--c
去除重复元素：
- 每当a，b或c移动后，都和移动前的位置比较一下。
- b和c仅需要在确定有结果后，才需要比较。因为如果a + b + c != 0，那么即使有重复也无所谓。

code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        auto res = vector<vector<int>>{};
        for(auto a = nums.begin(); a < nums.end(); ++a)
        {
            if(a != nums.begin() && *a == *(a - 1))
            {
                continue;
            }
            auto b = a + 1;
            auto c = nums.end() - 1;
            
            while(b < c)
            {
                if(*a + *b + *c < 0)
                {
                    ++b;
                }
                else if(*a + *b + *c > 0)
                {
                    --c;
                }
                else
                {
                    res.emplace_back<initializer_list<int>>({*a, *b, *c});
                    ++b;
                    --c;
                    while(b < c && *b == *(b - 1))
                    {
                        ++b;
                    }
                    while(b < c && *c == *(c + 1))
                    {
                        --c;
                    }
                }
            }
        }
        return res;
    }
};

LC259 较小的三数之和

排序后，固定i指针，移动j和k指针。

如果*i + *j + *k >= target，那么无论j移动到[j, k)之间的任何一个位置，也都有*i + *j + *k >= target。
如果*i + *j + *k < target，那么无论k移动到[j, k)之间的任何一个位置，都有*i + *j + *k < target，因此计数器应增加k - j个。

code

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        auto cnt = 0;
        for(auto i = nums.begin(); i < nums.end(); ++i)
        {
            auto j = i + 1;
            auto k = nums.end() - 1;
            while(j != nums.end() && j < k)
            {
                if(*i + *j + *k >= target)
                {
                    --k;
                }
                else
                {
                    cnt += k - j;
                    ++j;
                }
            }
        }

        return cnt;
    }
};

LC16 最接近的三数之和

仍然按照三数之和的代码进行，但是当sum != target时要差最小的sum。当sum == target时，直接返回sum。

code

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
    
        auto res = 0;
        auto dif = INT_MAX;
        for(auto i = nums.begin(); i < nums.end(); ++i)
        {
            auto j = i + 1;
            auto k = nums.end() - 1;
            while(j != nums.end() && j < k)
            {
                if(auto sum = *i + *j + *k;
                sum != target)
                {
                    if(dif > abs(sum - target))
                    {
                        dif = abs(sum - target);
                        res = sum;
                    }

                    if(sum > target)
                    {
                        --k;
                    }
                    else
                    {
                        ++j;
                    }
                }
                else
                {
                    return sum;
                }
            }
        }

        return res;
    }
};

LC18 四数之和

在三数之和外面再套一层循环即可。

code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        auto s = set<tuple<int, int, int, int>>{};
        for(auto a = nums.begin();a < nums.end(); ++a)
        {
            for(auto b = a + 1; b < nums.end(); ++b)
            {
                auto c = b + 1;
                auto d = nums.end() - 1;
                while(c < d)
                {
                    if(*a + *b + *c + *d < target)
                    {
                        ++c;
                    }
                    else if(*a + *b + *c + *d > target)
                    {
                        --d;
                    }
                    else
                    {
                        s.emplace(*a, *b, *c, *d);
                        ++c;
                        --d;
                    }
                }
            }
        }

        auto res = vector<vector<int>>(s.size());
        transform(s.begin(), s.end(), res.begin(), [](const auto& t) -> vector<int>
        {
            return apply([](auto... args) -> vector<int>
            {
                return {args...};
            }, t);
        });
        return res;
    }
};

454 四数相加 II

用一个hashmap去记录AB数组中的所有可能的和
遍历CD数组，寻找CD数组的和的相反数在hashmap中的个数

code

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        auto mp = unordered_map<int, size_t>{};
        for(auto a : A)
            for(auto b : B)
                ++mp[a + b];
        
        auto res = 0;
        for(auto c : C)
            for(auto d : D)
                if(mp.count(-(c + d)))
                    res += mp[-(c + d)];
        return res;
    }
};