LeetCode 2367算术三元组问题代码出现堆缓冲区溢出求助

题目描述 #

给定一个下标从0开始、严格递增的整数数组nums和正整数diff，若三元组(i,j,k)满足i<j<k、nums[j]-nums[i]==diff、nums[k]-nums[j]==diff，则该三元组为算术三元组。请计算满足条件的算术三元组的数目。

错误代码 #

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        int ans = 0;

        for (int i = 0; i < nums.size() - 2; i++) {
            for (int j = i + 1; i < nums.size() - 1; j++) {
                if (nums[j] - nums[i] == diff) {
                    for (int k = j + 1; k < nums.size(); k++) {
                        if (nums[k] - nums[j] == diff) ans++;
                    }
                }
            }
        }

        return ans;
    }
};

报错信息（翻译后） #

22错误：AddressSanitizer：在地址0x503000000090处发生堆缓冲区溢出，程序计数器(pc)地址为0x558615c49233，基指针(bp)地址为0x7fffb82e42b0，栈指针(sp)地址为0x7fffb82e42a8

问题分析 #

代码的核心错误在于第二个for循环的终止条件写错了：原本应该判断j < nums.size() - 1，但你写成了i < nums.size() - 1。这会导致j在循环中不受数组长度限制地持续递增，最终超出数组下标范围，触发堆缓冲区溢出错误。

另外，利用数组严格递增的特性，当nums[j] - nums[i] > diff时，后续j增大只会让差值更大，此时可以直接跳出内层循环，优化执行效率。

修正后的代码 #

优化版三重循环解法 #

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                int curr_diff = nums[j] - nums[i];
                if (curr_diff == diff) {
                    for (int k = j + 1; k < n; k++) {
                        if (nums[k] - nums[j] == diff) {
                            ans++;
                            break; // 数组严格递增，找到一个k即可跳出
                        } else if (nums[k] - nums[j] > diff) {
                            break;
                        }
                    }
                } else if (curr_diff > diff) {
                    break; // 差值超过diff，后续j更大只会差值更大，直接跳出
                }
            }
        }
        return ans;
    }
};

哈希表高效解法（时间复杂度O(n)） #

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        int ans = 0;
        unordered_set<int> num_set(nums.begin(), nums.end());
        for (int num : nums) {
            if (num_set.count(num + diff) && num_set.count(num + 2 * diff)) {
                ans++;
            }
        }
        return ans;
    }
};

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