`

4Sum (C++实现)

 
阅读更多

Given an array S of n integers, are there elements abc, 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:

 

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • 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)

 

class Solution {  
public:  
    vector<vector<int> > fourSum(vector<int> &num, int target) {  
        vector<vector<int> > ret;  
        sort(num.begin(), num.end());  
        for(int i = 0; i < num.size(); ++i) {  
            if(i > 0 && num[i] == num[i-1]) continue;  
            for(int j = i + 1; j < num.size(); ++j) {  
                if(j > i+1 && num[j] == num[j-1]) continue;  
                int k = j + 1, l = num.size() - 1;  
                int tsum = target - num[i] - num[j];  
                while(k < l) {  
                    int t = num[k] + num[l];  
                    if (t > tsum) {--l;}  
                    else if (t < tsum) {++k;}  
                    else {  
                        vector<int> vec({num[i], num[j], num[k], num[l]});
                        ret.push_back(vec);  
                        while(num[++k] == num[k-1]);  
                        while(num[--l] == num[l+1]);  
                    }  
                }  
            }  
        }  
        return ret;  
    }  
};  

 

欢迎关注微信公众号——计算机视觉 

 

0
0
分享到:
评论

相关推荐

    matlab smooth函数C++实现_c++smooth函数_smoothC++_smooth_C++_smoothmatl

    C++实现的移动平均平滑算法相比于Matlab的`smooth`函数,可能存在性能上的优势,因为C++是编译型语言,运行速度通常更快。但同时,C++的实现可能需要更多的代码管理和调试工作。因此,在选择使用哪种语言实现数据...

    matlab smooth函数C++实现,matlab的smooth函数,C,C++

    本文将详细探讨如何在C++中实现MATLAB的`smooth`函数,特别关注移动平均平滑算法,并将其应用到实际项目中。 首先,MATLAB的`smooth`函数通常用于进行数据平滑,它可以采用多种平滑方法,如移动平均、指数平滑等。...

    C++实现GMM源码

    在本文中,我们将深入探讨如何使用C++实现GMM(高斯混合模型)分类模型。高斯混合模型是一种概率模型,常用于数据建模、聚类以及概率密度估计等任务。GMM假设数据是由多个高斯分布的混合物生成的,每个观测值都是由...

    md5摘要算法的C++实现源码

    在C++中实现MD5算法,主要涉及以下几个核心步骤和知识点: 1. **MD5基本原理**:MD5由四个不同的处理函数F、G、H、I以及四个32位的中间变量A、B、C、D组成。通过一系列的位运算(如左移、异或等)和特定的加法运算...

    md5sum-code_md5sum_md5sum工具_

    1. `Md5Sum.cpp`: 这是一个C++源代码文件,可能包含了实现MD5计算功能的类或函数。 2. `md5main.cpp`: 这应该是程序的主入口文件,它调用`Md5Sum.cpp`中的函数,处理命令行参数,并进行MD5计算。 3. `Md5Sum.h`: 这...

    傅里叶变换C++实现

    在这个C++实现的项目中,我们将重点讨论傅里叶变换的基本概念、C++编程技巧以及如何在Visual Studio 2008环境下进行开发。 傅里叶变换的基本概念: 傅里叶变换(Fourier Transform)是将一个离散或连续函数表示为其...

    快速傅里叶变换C++实现

    在“快速傅里叶变换C++实现”这个项目中,`MrFFT.cpp`和`MrFFT.h`是实现FFT的核心文件。`MrFFT.h`很可能包含了FFT类的定义,包括类的结构、成员函数等,而`MrFFT.cpp`则是该类的具体实现,包含实际的计算逻辑。下面...

    最小二乘法的C++实现

    2. C++实现: 在C++中,我们可以使用Eigen库来处理矩阵运算和求逆。首先,确保安装了Eigen库,然后可以按照以下步骤编写代码: ```cpp #include // 定义设计矩阵X和观测值向量y Eigen::MatrixXd X(data_size, m+...

    C++实现离散序列自相关与互相关

    本文将详细讲解如何利用C++实现离散序列的自相关和互相关计算。 自相关函数(Autocorrelation Function, ACF)是用来测量一个信号在不同时间延迟下的自我相似程度。对于离散序列`x[n]`,其自相关函数定义为: \[ R...

    C++实现two sum问题的暴力算法

    标题中的"C++实现two sum问题的暴力算法"指的是在C++编程语言中,解决一个经典算法问题——Two Sum。这个问题的基本需求是,给定一个整数数组nums和一个目标值target,找出数组中两个数的索引,使得它们的和等于目标...

    模糊K均值算法C++实现

    在C++实现模糊K均值算法时,通常包括以下几个关键步骤: 1. **初始化**: 首先,我们需要选择K个初始质心(centroid),这些质心可以随机选取或基于数据集中的样本点。这将作为聚类的起点。 2. **计算隶属度**: ...

    IDW插值算法C++版本

    **IDW插值算法C++实现详解** IDW(Inverse Distance Weighting,反距离加权)是一种常见的空间插值方法,常用于地理信息系统(GIS)中,用于估算未知点的属性值。它基于一个简单的原理:近处的点对目标点的影响大于...

    两个矩阵乘法c++实现

    通过上述步骤,我们已经成功地用C++实现了两个矩阵的乘法运算。这个程序允许用户输入任意大小的矩阵,并自动进行乘法计算,最后输出结果。在实际应用中,可能还需要考虑性能优化,例如使用多线程或向量化技术来加速...

    快速傅里叶变换(FFT)算法的C++实现

    本篇将详细探讨FFT算法的C++实现,以及相关的重要概念。 首先,理解离散傅里叶变换(DFT)是理解FFT的基础。DFT将一个有限长度的序列转换到频域,以分析信号的频率成分。DFT的公式为: \[ X[k] = \sum_{n=0}^{N-1}...

    线性回归c++实现

    总之,这个C++实现的线性回归项目提供了一个基本的机器学习模型训练框架,对于初学者理解线性回归的原理和梯度下降法的运用具有很好的参考价值。同时,它也展示了如何在实际编程中实现这些理论概念。通过阅读和理解...

    C++实现K均值函数

    以下是对C++实现K均值算法的详细解释。 1. **K均值算法概述** K均值算法的基本思想是通过迭代找到K个簇,使得每个数据点到其所属簇中心的距离之和最小。首先随机选择K个初始质心(或根据已有知识设定),然后将...

    二维傅里叶变换的C++实现

    本资源提供的就是一个C++实现的二维FFT程序,它包含了多个示例,方便学习和理解。 首先,我们要了解什么是傅里叶变换。傅里叶变换是一种数学工具,它可以将一个信号或函数从时域(或空域)转换到频域,揭示信号的...

    C++ 实现DCT算法

    下面我们将深入探讨DCT的基本原理、C++实现DCT的关键步骤以及相关文件的作用。 一、离散余弦变换(DCT)原理 离散余弦变换是将时域信号转换到频域的一种方法。它通过一组正交基函数(余弦函数)对信号进行线性组合...

    用c++实现动态规划求最大字段和

    总之,通过C++实现的动态规划算法,我们可以高效地找到数组中的最大字段和,这种方法不仅简洁,而且易于理解,是处理这类问题的标准方法。在学习和使用过程中,理解动态规划的思想和步骤,以及如何将其转化为代码,...

    P11_梯形积分公式的C++实现_

    在本项目中,我们关注的是"梯形积分公式"的C++实现,这是一种简单的数值积分方法,常用于计算机科学和工程计算。下面将详细介绍梯形规则以及如何在C++中实现它。 梯形法则基于基本的几何思想:将一个曲边梯形的面积...

Global site tag (gtag.js) - Google Analytics