为何LeetCode 1855题代码1超内存限制而代码2正常运行？

两段代码的核心差异在于数组传递方式，这直接导致了内存开销的天差地别：

第一段代码内存超限的根源 #

第一段代码中，binarySearch函数的第一个参数是vector<int> nums——这是传值传递。每次调用binarySearch(nums2, ...)时，程序都会完整复制整个nums2数组，生成一个新的副本供函数使用。

假设nums2的长度为m，nums1的长度为n，那么整个循环过程中，数组复制的总空间开销是O(n*m)。当测试用例的数组规模较大时（比如长度达到10^5级别），这种重复复制会迅速耗尽内存，触发「内存超限」错误。

第一段代码：

class Solution {
public:
    int binarySearch(vector<int> nums, int l, int h, int target) {
        int res=-1;
        
        while(l<=h) {
            int mid = (l+h)/2;
            if(nums[mid] >= target)
            {
                res=mid;
                l=mid+1;
            }
            else h=mid-1;
        }     
        return res;
    }
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int maxi = 0;
        
        for(int i=0; i<nums1.size(); i++) {
            int ind = binarySearch(nums2, i, nums2.size()-1, nums1[i]);
            if(ind != -1) {
                maxi=max(ind-i, maxi);
            }
        }
        
        return maxi;
    }
};

第二段代码正常运行的原因 #

第二段代码将二分查找逻辑直接内联在主函数中，全程直接操作原数组nums2，没有任何数组复制操作。所有变量都是单个整数，空间复杂度保持为常数级O(1)，不会产生额外的内存开销，因此可以正常通过所有测试用例。

第二段代码：

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int maxi = 0;
        
        for(int i=0; i<nums1.size(); i++) {
            int h=nums2.size()-1, l=i;
            while(l<=h) {
                int mid = (l+h)/2;
                if(nums2[mid] >= nums1[i])
                {
                    maxi=max(mid-i, maxi);
                    l=mid+1;
                }
                else h=mid-1;
            }
        } 
        
        return maxi;
    }
};

第一段代码的修复方案 #

只需将binarySearch函数的参数改为传引用，避免数组复制：

// 修改参数为引用
int binarySearch(vector<int>& nums, int l, int h, int target) {
    // 函数逻辑不变
}

修改后，函数会直接操作原数组，空间复杂度降至O(1)，即可解决内存超限问题。

内容的提问来源于stack exchange，提问作者Vishu Kaushik