18.四数之和

算法 LeetCode 双指针剪枝

字数统计: 697阅读时长: 3 min

 2022/07/29 

双指针+排序+剪枝

和三数之和类似，只不过多了一重循环。也就是先对nums数组进行排序，前面是两重循环从小到大遍历，再用两个指针，一个从前往后一个从后往前，并列关系，即双指针可以去除掉一重循环的时间复杂度
但这道题要考虑有符号数溢出的问题，所以要考虑对数据进行剪枝：剪枝方法看代码注释。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        vector<vector<int>> b;
        int n = nums.size();
        if(n<4) return b;
        //数组排序
        sort(nums.begin(), nums.end());

        for(int i=0; i<n-3; i++){
            //对第一个数进行去重
            if(i>0 && nums[i]==nums[i-1])
                continue;
            //由于是已经从小到大进行排序了，所以若当前数及其后三个数的和（本轮最小）
            //已经大于target了，那么后面肯定不存在符合题意的解了，可以直接退出循环。
            if((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target)
                break;
            //同理，若是当前数和倒数三个数的和（本轮最大）依然小于target，那么
            //当前这个i太小了，应该直接跳过，i自增，进入下一重循环。
            if((long)nums[i]+nums[n-1]+nums[n-2]+nums[n-3] < target)
                continue;

            for(int j=i+1; j<n-2; j++){
                //对第二个数进行去重
                if(j>i+1 && nums[j]==nums[j-1])
                    continue;
                //若当前i和j下的两个数及其后两个数的和（本轮最小）已经大于target了，
                //那么后面肯定不存在符合题意的解了，可以直接退出循环。
                if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2] > target)
                    break;
                //同理，若是当前i和j下固定的两个数和倒数两个数的和（本轮最大）
                //依然小于target，那么当前这个j太小，应该直接跳过，进入下一重循环。
                if((long)nums[i]+nums[n-1]+nums[n-2]+nums[j] < target)
                    continue;
                //双重指针
                int right = n-1;
                int left = j+1;

                while(left<right)
                {
                    int sum = nums[i]+nums[j]+nums[left]+nums[right];
                    //找到解
                    if(sum==target){
                        b.push_back({nums[i], nums[j], nums[left], nums[right]});
                        //对left去重，注意left<right条件要先判断，写在后面若left在边界
                        //也就是left+1溢出了编译器会报错！！！
                        while(left<right && nums[left]==nums[left+1])
                            left++;
                        //找到答案移动指针
                        left++;

                        //对right去重，注left<right条件要先判断，写在后面若right在边界
                        //也就是right-1溢出了编译器会报错！！！
                        while(left<right && nums[right]==nums[right-1])
                            right--;
                        //找到答案移动指针
                        right--;
                    }
                    else if(sum>target)
                        right--;
                    else
                        left++;
                }
            }
        }
        return b;
    }
};

Next Post

七月的最后一个周末
Previous Post

142.环形链表Ⅱ

CATALOG

1. 双指针+排序+剪枝