[LeetCode]18.4Sum

本文主要是介绍[LeetCode]18.4Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

    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)

【题意】

给定n个整数的数组S，是否在 数组S中有元素a，b，c，d，使得a + b + c + d = target？在数组中找出独一无二的四元素组，使得他们之和为target。

注意：

在四元素组（a，b，c，d）中，必须满足非递减排序。 （即a≤b≤c≤d）

该解决方案集中一定不能包含重复的四元素组。

【分析】

1. 对数组排序
2. 确定四元数中的前两个（a，b）
3. 遍历剩余数组确定两外两个（c，d），确定cd时思路跟3Sum确定后两个数据一样，二分查找左右逼近。
4. 在去重时采用set集合

【代码】

/*********************************
*   日期：2014-01-18
*   作者：SJF0115
*   题号: 4Sum
*   来源：http://oj.leetcode.com/problems/4sum/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;class Solution {
public:vector<vector<int> > fourSum(vector<int> &num, int target) {int i,j,start,end;int Len = num.size();vector<int> triplet;vector<vector<int>> triplets;set<vector<int>> sets;//排序sort(num.begin(),num.end());for(i = 0;i < Len-3;i++){for(j = i + 1;j < Len - 2;j++){//二分查找start = j + 1;end = Len - 1;while(start < end){int curSum = num[i] + num[j] + num[start] + num[end];//相等 -> 目标if(target == curSum){triplet.clear();triplet.push_back(num[i]);triplet.push_back(num[j]);triplet.push_back(num[start]);triplet.push_back(num[end]);sets.insert(triplet);start ++;end --;}//大于 -> 当前值小需要增大else if(target > curSum){start ++;}//小于 -> 当前值大需要减小else{end --;}}//while}}//for//利用set去重set<vector<int>>::iterator it = sets.begin();for(; it != sets.end(); it++)triplets.push_back(*it);return triplets;}
};
int main() {vector<vector<int>> result;Solution solution;vector<int> vec;vec.push_back(-3);vec.push_back(-2);vec.push_back(-1);vec.push_back(0);vec.push_back(0);vec.push_back(1);vec.push_back(2);vec.push_back(3);result = solution.fourSum(vec,0);for(int i = 0;i < result.size();i++){for(int j = 0;j < result[i].size();j++){printf("%d ",result[i][j]);}printf("\n");}return 0;
}

【测试】

这篇关于[LeetCode]18.4Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！