c++ - 为什么相似的代码具有不同的运行时和内存使用率？

我使用递归解决了leetcode上的this问题。我研究了不同版本的解决方案后发现运行时和内存使用情况随多个参数而变化，当我从for循环切换到while循环时，运行时间从92毫秒减少到56毫秒。我还使用了其他冗余，将其删除后，运行时间将从56ms进一步减少到40ms，内存使用情况保持不变。我看到了另一个解决方案，该解决方案比我的要快得多，并且只使用了三分之一的内存。我的最终版本几乎与我看到的版本相似，但仍然慢了一倍。
我的解决方案:

    class Solution {
public:
      static void solver(vector<int>candidates, int target, vector<int> path, int index, vector<vector<int>>&res){
          if(target == 0){
              if(find(res.begin(), res.end(), path) == res.end())
              res.push_back(path);
              return;
          }
          else if(target < 0){
              return;
          }

          else{

            //   both of these work!!! but for loop(92ms) is slower than while loop(56ms) memory usage being 28MB.
            // If I remove else further runtime would improve to 40ms

            //   for(int i = index; i< candidates.size() && target-candidates[i] >= 0; i++){
            //       path.push_back(candidates[i]);
            //       solver(candidates, target-candidates[i], path, i+1, res);
            //       path.pop_back();
            //   }

            while(index < candidates.size() && target-candidates[index] >= 0){
                path.push_back(candidates[index]);
                solver(candidates, target-candidates[index], path, index+1, res);
                index++;
                path.pop_back();
            }
          }
      }

      static vector<vector<int>> combinationSum2(vector<int>&candidates, int target){
          vector<vector<int>> res;
          vector<int> path;
          int index{0};
          sort(candidates.begin(), candidates.end());
          solver(candidates, target, path, index, res);
          return res;
      }


};

我发现的解决方案:
它比上面的任何骇客都要快，花费了20毫秒和10.8MB的空间。即使我的最终版本几乎与此版本相似，也可能是原因。

 vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
    {
         vector<vector<int>> sol;
         vector<int> v;
        sort(candidates.begin(),candidates.end());
         int i=0;
         permute(candidates,target,i,v,sol);
        return sol;
    }
    void permute(vector<int>& candidates,int target,int i,vector<int> &v,vector<vector<int>> &sol)
    {
        if(target==0)
        {
            if(find(sol.begin(),sol.end(),v)==sol.end())
                sol.push_back(v);
            return;
        }
        if(target<0)
            return;
        while(i<candidates.size() && target-candidates[i]>=0)
        {
            v.push_back(candidates[i]);
             permute(candidates,target-candidates[i],i+1,v,sol);
            i++;
             v.pop_back();
        }
    }

在for循环中，会有变量i的额外副本，这在其他方面可以理解。

最佳答案

关键区别很可能是permute通过引用获取candidates和path vector 。

void permute(vector<int>& candidates,int target,int i,vector<int> &v,vector<vector<int>> &sol)

另一方面，solver复制 vector 。

static void solver(vector<int>candidates, int target, vector<int> path, int index, vector<vector<int>>&res)

由于该函数在递归中被反复调用，因此这可能会增加大量的内存和时间。

关于c++ - 为什么相似的代码具有不同的运行时和内存使用率？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/63180496/