假设我们有一个由n个数字组成的数组;我们必须找到一个非空子集,以使子集的元素之和可被n整除。因此,我们必须输出任何此类子集及其大小和原始数组中元素的索引(如果存在)。
因此,如果输入类似于[3,2,7,1,1,9],则输出将为[2],[1 2]。
为了解决这个问题,我们将遵循以下步骤-
定义一张映射my_map
加:= 0
对于初始化i:= 0,当i <N时,更新(将i增加1),执行-
my_map [add]:= i
打印(i-my_map [add])
对于初始化j:= my_map [add] + 1,当j <= i时,更新(将j增加1),执行-
返回
打印j + 1
打印i + 1
对于初始化j:= 0,当j <= i时,更新(将j增加1),执行-
返回
打印j + 1
加:=(加+ arr [i])mod N
如果add与0相同,则-
如果添加到my_map中,则-
除此以外
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; void subset_find(int arr[], int N) { unordered_map<int, int> my_map; int add = 0; for (int i = 0; i < N; i++) { add = (add + arr[i]) % N; if (add == 0) { cout << i + 1 << endl; for (int j = 0; j <= i; j++) cout << j + 1 << " "; return; } if (my_map.find(add) != my_map.end()) { cout << (i - my_map[add]) << endl; for (int j = my_map[add] + 1; j <= i; j++) cout << j + 1 << " "; return; } else my_map[add] = i; } } int main() { int arr[] = {3, 2, 7, 1, 9}; int N = sizeof(arr) / sizeof(arr[0]); subset_find(arr, N); }
{3, 2, 7, 1, 9}
输出结果
2 1 2