确定大O：在数组中找到4个不同的数字，求和为S

Question

给定一个数arr和一个数S的数组，在arr中找到4个不同的数，其总和为S。

编写一个函数，获取arr和S，并返回一个数组，其中包含arr中此类数字的4个索引。

我提出的解决方案涉及递归地建立索引组合，同时确保不会多次计算组合。我还通过确保解决方案集的大小不超过4来修剪搜索树。

#include <iostream>
#include <vector>
using namespace std;

bool find_sol(vector<int> &N, vector<int> &I, int S, int sum){
  if (I.size() == 4)
    if (S == sum)
      return true;
    else
      return false;
  for (int i = 0; i < N.size(); ++i){
    if (I.empty() || I[I.size()-1] < i){
      I.push_back(i);
      if (find_sol(N,I,S,sum+N[i]))
        return true;
      else {
        I.pop_back();
      }
    }
  }
  return false;
}

int main(){
  int S = 23;
  vector<int> numbers = {1,3,5,6,7,8,9};
  vector<int> indices;
  find_sol(numbers,indices,S,0);

  // prints 0, 2, 5, 6
  for (int i = 0; i < indices.size(); ++i)
    cout << indices[i] <<" ";
  cout<<endl;

  return 0;
}

我如何确定这个算法的运行时间？我觉得它类似于O（n选择4），但不确定。解决方案告诉我最佳运行时间是O（n^2）。

Answer 1

您的解决方案确实是O（nC4）=O（n^4），因为它会找到所有可能的组合并检查它们——对于每个组合，都需要不断的额外工作。

它可以在O（n^2）中通过首先填充哈希映射（std::unordered_map）来完成，其中键是数组中所有对的求和，并且值指向这些值的索引。填充此映射是O（n^2）平均大小写。

然后，再次迭代所有对，对于带有sumd的每对i， j，在哈希映射中查找是否有带有keyS-d的条目。

注意：您还需要确保此条目不包含来自i， j的索引。为了能够处理它，您的map值实际上可能是一个成对向量。

作为旁注，这个问题被称为子集求和问题，放宽了4个元素正好与目标求和的限制（经典问题对此没有限制）