LeetCode 494目标和：错误代码运行时错误原因排查

错误现象 #

运行时触发内存访问溢出错误：

Line 1034: Char 34: runtime error: addition of unsigned offset to 0x6250004d0900 overflowed to 0x6250004cf960 (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

错误代码 #

//Incorrect code
class Solution {
public:
    
    int fun(vector<int>& nums, int target,int n ,vector<vector<int>> &dp){
        if(n  == 0){
            if(target == 0) return 1;
            return 0;
            }
        
        if(dp[n][target+1000] != -1) return dp[n][target+1000];
        return dp[n][target+1000] =  fun(nums,target - nums[n-1],n-1,dp) + fun(nums,target + nums[n-1],n-1,dp);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
       vector<vector<int>> dp(21,vector<int>(2001,-1));
       return fun(nums,target,nums.size(),dp);
    }
};

正确代码 #

//Correct code
class Solution {
public:
    int dp[21][2001];

    int fun(int i,int sum,int target,vector<int>&nums){
        if(i == nums.size()){
            if(sum == target) return 1;
            return 0;
        }
        if(dp[i][sum+1000] != -1) return dp[i][sum+1000];
        return dp[i][sum+1000]  = fun(i+1,sum+nums[i],target,nums) + fun(i+1,sum-nums[i],target,nums);  
    }

    int findTargetSumWays(vector<int>& nums, int target) {
        memset(dp,-1,sizeof(dp));
        return fun(0,0,target,nums);
    }
};

问题原因分析 #

原代码的核心问题是递归过程中访问dp数组时发生索引越界：

• 原代码递归逻辑是从数组末尾往头部遍历，每次对target执行±nums[n-1]操作，导致target的取值范围可能超出[-1000, 1000]。
• 当target超出该范围时，target+1000的结果会落在0~2000之外：
  • 若target > 1000，则target+1000 > 2000，超出dp第二维的最大索引（2000）；
  • 若target < -1000，则target+1000 < 0，由于vector的索引是无符号整数，负数会被转换为极大的无符号值，同样触发越界访问。
• 正确代码的递归逻辑是从数组头部往末尾遍历，sum从0开始逐步累加/减去元素值，结合题目限制（nums长度≤20，每个元素≤100），sum的取值范围始终被控制在[-1000, 1000]，sum+1000的结果刚好落在dp第二维的合法索引范围内，不会触发越界。

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