c++ - 返回 2d vector 中索引 i、j 的所有组合，总和为所需值

Question

我有一个二维 vector v (所有值为正，二维矩阵为方阵)和给定值k .例如，

v={
   {2,1},
   {3,4}
  }

k = 3

我想查找并存储 i, j 的所有这些组合这样

arr[i] + arr[j] = k, or
arr[i] = k, or
arr[j] = k

例如v[0][0] + v[0][1] = 3 & v[1][0] = 3 .我想将这些对存储在这样的数组中 std::vector<std::vector<std::pair<int, int>>> .

Sample input:
v={
   {2,1},
   {3,4}
  }

k = 3

Sample output:
{{(0,0),(0,1)}, {(1,0)}}

我工作的各个部分；

#include<iostream>
#include<vector>
int main(){
    using namespace std;
    vector<vector<int>>v={{2,1},{3,4}};
    vector<pair<int,int>>k;
    int size=v.size();
    for(size_t i=0;i<size;i++){
        for(size_t j=0;j<size;j++){
            if(v[i][j]==3){
                k.push_back(make_pair(i,j));
            }     
        }
    }
}

编辑 link对于我以上述方式感知并尝试解决的实际问题。

Answer 1

编辑

我给出的第一个答案是考虑可以选择任意数量的元素来形成目标总和。但由于我们最多只能取 2 个，所以这里进行修改。

如果两个元素组成目标和，要点是当你输入一个元素x , 如果我们已经输入了 y = target - x过去的元素，对 x所有出现的 y .

下面是应该很容易理解的代码。

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, pii> PIJ;

int main() {
    int N, target;
    cin >> N >> target;

    vector<vector<int>> matrix(N, vector<int>(N));
    unordered_map<int, vector<pii>> M;
    vector<PIJ> res;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            int x;
            cin >> x;

            matrix[i][j] = x;

            int y = target - x;
            for (const pii& p: M[y])
                res.emplace_back(p, make_pair(i, j));

            M[x].emplace_back(i, j);
        }
    }
}

---

考虑一维长度的问题 n第一的。最天真的算法是形成所有 2^n-1组合并检查每个元素是否总计为 target .

幸运的是，相同的搜索空间可以被遵循最优子结构属性的另一种算法耗尽。让count(i, t)代表第一个i的组合总数总计为 t 的元素.那么count(i, t) = count(i-1, t-arr[i]) + count(i-1, t) .基本条件为 t = 0。 .如果0可以出现在输入数组中，那么您将不得不考虑到这一点。会有重叠的子问题，需要动态规划。

保持运行数组chosen每次选择一个值时(调用 count(i-1, t-arr[i]) 时)，将索引插入 chosen如果达到基本条件，请推送 chosen 的拷贝进入你的说法combinations大批。当控件返回到您调用 count(i-1, t-arr[i]) 的位置时, 将此值弹出 chosen .

您的二维问题可以转换为一维数组 pair<int, int>并且可以应用相同的算法。