【题目】
Given an arraySofnintegers, are there elementsa,b,c, anddinSsuch
thata+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)
【题意】
给定n个整数的数组S,是否在 数组S中有元素a,b,c,d,使得a + b + c + d = target?在数组中找出独一无二的四元素组,使得他们之和为target。
注意:
在四元素组(a,b,c,d)中,必须满足非递减排序。 (即a≤b≤c≤d)
该解决方案集中一定不能包含重复的四元素组。
【分析】
- 对数组排序
- 确定四元数中的前两个(a,b)
- 遍历剩余数组确定两外两个(c,d),确定cd时思路跟3Sum确定后两个数据一样,二分查找左右逼近。
- 在去重时采用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;
}
【测试】
Input: |
[-1,0,1,2,-1,-4], -1 |
|
|
Expected: |
[[-4,0,1,2],[-1,-1,0,1]] |
Input: |
[-3,-2,-1,0,0,1,2,3], 0 |
|
|
Expected: |
[[-3,-2,2,3],[-3,-1,1,3],[-3,0,0,3],[-3,0,1,2],[-2,-1,0,3],[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] |
分享到:
相关推荐
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
Leetcode two sum java 解法
oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)
leetcode 2SUM 使用以前的地图最快的 2Sum O(N) 使用 unordered_map 比 map 快 以前的地图 là gì ? 上一张地图 đơn giản là 地图 nhưng thay vì ta cần một vòng for để khởi tạo 地图 thì ta khởi...
个数字之和等于该元素的相反数字? 如果有,请将这两个数字附加到我们的列表中,稍后我们将返回。 代码如下: class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: def search_sum(target,num...
3sum # Leetcode 解决方案以下是我在 Leetcode 上解决的一些问题,如果你喜欢/找到任何你的答案,请留下一个星。 如果你想与我联系,我在下面分享了我的 Linkedin URL。 问题 # 标题 # 解决方案 困难 1 二和 简单...
python python_leetcode面试题解之两数之和TwoSum
LeetCode — Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need...
python python_leetcode面试题解之三数之和_3sum
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
18| [4 Sum](https://leetcode.com/problems/4sum/) | [C++](./C++/4sum.cpp) [Python](./Python/4sum.py) | _O(n^3)_ | _O(1)_ | Medium || Two Pointers 26 | [Remove Duplicates from Sorted Array]...
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp - 键盘.cpp - 2Sum_Data_Structure_Design.cpp - shuffle_array.cpp - permutations.cpp - kth_missing_...
Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest Substring Without Repeating Characters LeetCode 13 Roman to ...
Leetcode 1 two sum C++ code
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2)...
Leetcode\TwoSum\TwoSum.cs 问题: 业绩报告: 反转整数 代码: Leetcode\ReverseInteger\ReverseInteger.cs 问题: 业绩报告: 回文数 代码: Leetcode\PalindromeNumber\PalindromeNumber.cs 问题: 从排序数组中...
leetcode两数之和代码 题目描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个...
leetcode 2sum leetCode解决方案 我对 leetCode 问题的解决方案 已解决的练习列表: 简单的: 2sum - 带有未排序的数组; O(n) 复杂度; 花了~3ms 2sum - 使用排序数组; O(n) 复杂度 罗马转整数; O(n) 复杂度 合并...