关于四数之和代码的相关问题

Question

在18四数之和的算法题中，使用如下代码

var fourSum = function (nums, target) {
    // 定义四个指针k指向数组首位，i指向k后一位，left指向i后一位，right指向数组末尾
    // nums[k]+nums[i]+nums[left]+nums[right]=target
    let k = 0, i = k + 1, left = i + 1, right = nums.length - 1;
    // 定义res数组保存结果集
    let res = [];
    // 对数组进行排序
    nums.sort((a, b) => a - b);
    //    k指针遍历
    for (; k < nums.length; k++) {
        // 如果排序后数组第一位就大于target，那就不必继续了，越加越大
        if (nums[k] > target && nums[k] > 0 && target > 0) break;
        // 对k指针遍历的数组元素去重
        if (k > 0 && nums[k] == nums[k - 1]) continue;
        // i指针遍历
        for (i = k + 1; i < nums.length; i++) {
            // 若前两个指针所指向数组元素之和大于target，同理，越加越大不必再加
            if (nums[k] + nums[i] > target && nums[k] + nums[i] > 0 && target > 0) break;
            // 对i指针遍历的数组元素去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            while (left < right) {
                // 左右指针所指向的元素去重
                //     if(nums[left] == nums[left - 1]) continue;
                //    if (nums[right] == nums[right + 1]) continue;
                const sum = nums[k] + nums[i] + nums[left] + nums[right];
                if (sum > target) right--;
                if (sum < target) left++;
                res.push([nums[k], nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[++left]);
                while (left < right && nums[right] === nums[--right]);


            }
        }
    }
    return res
};

根据代码注释找出代码中存在什么错误导致没有通过测试用例

Answer 1

var fourSum = function(nums, target) {
    const len = nums.length;
    if(len < 4) return [];
    nums.sort((a, b) => a - b);
    const res = [];
    for(let i = 0; i < len - 3; i++) {
        // 去重i
        if(i > 0 && nums[i] === nums[i - 1]) continue;
        for(let j = i + 1; j < len - 2; j++) {
            // 去重j
            if(j > i + 1 && nums[j] === nums[j - 1]) continue;
            let l = j + 1, r = len - 1;
            while(l < r) {
                const sum = nums[i] + nums[j] + nums[l] + nums[r];
                if(sum < target) { l++; continue}
                if(sum > target) { r--; continue}
                res.push([nums[i], nums[j], nums[l], nums[r]]);
                while(l < r && nums[l] === nums[++l]);
                while(l < r && nums[r] === nums[--r]);
            }
        } 
    }
    return res;
};

这段代码实现的是“四数之和”（4Sum）问题的解决方案，主要思路是使用排序加上双指针技术来查找所有可能的四元素组合，使得这四个数的和等于目标值 target。下面是具体的思路解析：

1. 排序：首先对数组 nums 进行排序。排序可以减少后续查找的时间复杂度，同时方便我们去重和使用双指针。

2. 固定两个数，双指针查找其他两个数：

   • 我们用两个循环分别固定数组中的前两个数 nums[i] 和 nums[j]。
   • 然后使用双指针 l 和 r（分别指向 j + 1 和 nums.length - 1）来尝试寻找另外两个数，使得四数之和等于 target。
   • 双指针根据当前四数之和与目标值的比较结果来移动：如果当前和小于目标值，就将左指针 l 右移；如果当前和大于目标值，就将右指针 r 左移；如果当前和等于目标值，就将该组合存入结果数组 res。

3. 去重：为了避免重复计算相同的四元组，当 i 和 j 移动时，如果当前值与前一个值相同，则跳过这次循环，直接进行下一次循环。对于 l 和 r，在找到符合条件的组合后，同样需要进行去重处理，避免重复的四元组被加入结果数组。

4. 结果返回：最后，返回存储所有符合条件的四元组的数组 res。

这种算法的时间复杂度是 O(n³)，因为我们需要遍历数组三次（两次循环和一次双指针遍历）。使用双指针技术可以避免了对第三个和第四个数的再次遍历，从而降低了时间复杂度。同时，排序操作的复杂度是 O(n log n)，但通常不会成为瓶颈。