leetcode_4Sum笔记

        Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

        博主的答案最后是TLE,虽然代码正确,但是算法耗时太长,算法复杂度为O(N^4),以下是博主代码:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<int> array;
        vector<int> array_target;
        vector<vector<int>> result;
        vector<vector<int>> finish;
        std::sort(nums.begin(), nums.end());
        if(nums.size() < 4) return finish;
        //array = reduceCheck(nums);
        array = nums;
        for(int i = 0; i < array.size()-3; i++){
            for(int j = i+1; j < array.size()-2; j++){
                for(int k = j+1; k < array.size()-1; k++){
                    for(int l = k+1; l < array.size(); l++){
                        array_target.clear();
                        if(target == (array[i] + array[j] + array[k] + array[l])){
                            array_target.push_back(array[i]);
                            array_target.push_back(array[j]);
                            array_target.push_back(array[k]);
                            array_target.push_back(array[l]);
                            result.push_back(array_target);
                        }
                    }
                }
            }
        }
        finish = CheckSame(result);
        return finish;
    }
protected:
    vector<vector<int>> CheckSame(vector<vector<int>>& array){
        vector<vector<int>> result;
        for(int i = 0; i < array.size(); i++){
            if (i==0){
                result.push_back(array[i]);
                continue;
            }
            bool flag = false;
            for(int j = 0; j < i; j++){
                if(array[i] == array[j]){
                    flag = true;
                    break;
                }
            }
            if(flag == false){
                result.push_back(array[i]);
            }
        }
        return result;
    }
};

        是的,博主在写代码时没有考虑算法复杂度的问题,并且对一些技巧不太了解,下面就来解析一个算法复杂度为O(N^3)的代码:

/**
 * 本代码由九章算法编辑提供。没有版权欢迎转发。
 * - 九章算法致力于帮助更多中国人找到好的工作,教师团队均来自硅谷和国内的一线大公司在职工程师。
 * - 现有的面试培训课程包括:九章算法班,系统设计班,九章强化班,Java入门与基础算法班
 * - 更多详情请见官方网站:http://www.jiuzhang.com/
 */



class Solution {
public:
    /*
    题意:找到数列中所有和等于目标数的四元组,需去重
    多枚举一个数后,参照3Sum的做法,O(N^3)
    */
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int len = nums.size();
        int left, right, sum;
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> tmp;
        for (int i = 0; i < len - 3; i++) {
            if (i && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < len - 2; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) continue;
                sum = target - nums[i] - nums[j];
                left = j + 1;
                right = len - 1;
                while (left < right) {
                    if (nums[left] + nums[right] == sum) {
                        tmp.clear();
                        tmp.push_back(nums[i]);
                        tmp.push_back(nums[j]);
                        tmp.push_back(nums[left]);
                        tmp.push_back(nums[right]);
                        res.push_back(tmp);
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    } else 
                        if (nums[left] + nums[right] > sum) right--;
                        else left++;
                }
            }
        }
        return res;
    }
};

        确实比博主的代码简洁多了,下面介绍其中的一些技巧:

    1.nums在使用前进行排序

★2.通过相邻相等的判断,实现了相同答案的滤除

★3.在降低算法复杂度方面,从一个数组中取出四个数的方法,先从其中取出两个,都是从左向右,后两个数如果也这样取,那就是O(N^4),所以以下代码至关重要:

                left = j + 1;
                right = len - 1;
                while (left < right) {
                    if (nums[left] + nums[right] == sum) {
                        tmp.clear();
                        tmp.push_back(nums[i]);
                        tmp.push_back(nums[j]);
                        tmp.push_back(nums[left]);
                        tmp.push_back(nums[right]);
                        res.push_back(tmp);
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    } else 
                        if (nums[left] + nums[right] > sum) right--;
                        else left++;
                }

        注意这个if、else,我们要处理的问题是固定和,如果已经有一个答案了,那么原先的基础上的两个值都要改变,不能只改变一个,如果目前没有答案,那我们只改变其中一个值,直到遇到答案,这里有一个大小相对变化的问题,不用担心漏掉,这样就把算法复杂度降低了一个数量级O(N^3)。

        总体来说,就是将两个数确定下来之后,剩下的是一个定和问题,从而使用低算法复杂度的算法。当然,这份代码效率也并不是很高,还有其它更快的算法比较常见的是使用hash表,还有其它另人瞠目的算法,无奈博主水平有限,以后有机会再介绍吧。

        OK,See You Next Chapter!

发表评论