Leetcode 18四数之和（双指针+简单剪枝）-白红宇

Leetcode 18四数之和（双指针+简单剪枝）

阅读量：708 次

发布时间：2019-03-21

本文共 1701 字，大约阅读时间需要 5 分钟。

四数之和问题的解法

在leetcode上，四和问题（四数之和）的解法通常使用暴力的双指针方法结合剪枝优化。这种方法在时间复杂度上虽然看似O(n^4)，但通过剪枝可以将实际运行时间大幅降低。

解题思路

将数组先进行排序，这样可以方便后续的剪枝。然后通过外层循环固定前三个元素，内层循环使用双指针遍历数组的最后两个元素。

在这个过程中，我们主要使用两种剪枝策略：

前缀剪枝：如果前三个固定元素之和已经超过了目标值，直接终止循环，因为后续的元素之和只会更大。

重复剪枝：如果当前元素与前一个元素相等，跳过重复的元素，避免重复计算。

这种方法能显著减少不必要的计算，优化了效率。

伪代码实现

class Solution {public:    vector
   
    
     > fourSum(vector
     
       &nums, int target) {        vector
      
       
        > ans;        int len = nums.size();        if (len < 4) return ans;        sort(nums.begin(), nums.end());        // 外层循环固定i，j是右指针        for (int i = 0; i <= len - 4; ++i) {            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)                break; // 前缀剪枝            if (i > 0 && nums[i] == nums[i - 1])                continue; // 重复剪枝            // 内层双指针            int j = i + 1;            for (int j = i + 1; j <= len - 3; ++j) {                if (nums[j] + nums[j + 1] + nums[j + 2] + nums[i] > target)                    break;                if (j > i + 1 && nums[j] == nums[j - 1])                    continue;                // 双指针开始                int l = j + 1, r = len - 1;                while (l < r) {                    int sum = nums[i] + nums[j] + nums[l] + nums[r];                    if (sum == target) {                        vector
        
          temp; temp.push_back(nums[i], nums[j], nums[l], nums[r]); while (l < r && nums[l] == nums[l + 1]) ++l; while (r > l && nums[r] == nums[r - 1]) --r; ans.push_back(temp); } else if (sum < target) { ++l; } else { --r; } } } } return ans; }};

优化说明

通过对数组进行排序，我们可以利用前缀的剪枝策略，快速跳过不可能满足条件的组合。同时，利用双指针的方法可以精确地找到符合条件的组合。由于数组是有序的，这种方法避免了重复计算重复的元素组合，减少了运行时间。

转载地址：http://iymez.baihongyu.com/

你可能感兴趣的文章