网上4个加法合成的20以内加减法填空题

来源：蜘蛛抓取(WebSpider) 时间：2016-09-14 12:41 标签： 20以内填空加减法
Question：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.
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:
(-2, -1, 1, 2)
0, 0, 2)给定一个n个数的数组S，判断存在不存在这样的a,b,c,d使a+b+c+d=target,找出所有的符合条件的值，注意，必须满足a&=b&=c&=d,举个例子说，比如数组S={1,0，-1,0，-2,2}target=0，那么答案是(-1,
0, 0, 1)(-2, -1, 1, 2) (-2,
0, 0, 2)。
算法思路：① 这个题和上两篇文章三个数的和类似，上两篇用的是穷举算法，这次总不能再用穷举吧，下面是比较好理解时间复杂度又比较小的一种算法。　　　　　② 首先对数组进行排序，设置两个for循环，作为四个数中的前两个数，有可能有两个相同的数，遇到相同的数跳过，这样做是为了避免重复。　　　　　③ 四个数中的后两个数怎么办，通过设置两个指针m和n,m从数组前往后进行遍历，n用来从数组后往前进行遍历。m&=n是结束循环的条件。　　　　　④ 遇到target==a+b+c+d的数就加到Arraylist中.
代码设计（）：
1 class Solution{
public ArrayList&ArrayList&Integer&& fourSum(int[] num, int target) {
// 4个数的和再使用穷举算法时间复杂度就太高了
ArrayList &ArrayList&Integer&& arrayList=new ArrayList&ArrayList&Integer&&();//最终返回的容器类型
Arrays.sort(num);
for(int i=0;i&num.i++){//三重循环时间复杂度太高， 可是也没想起其他好办法
if(i!=0&&num[i]==num[i-1])
continue;//如果两个数连着相等，直接越过这个数就可以
for(int j=i+1;j&num.j++){
if(j!=i+1&&num[j]==num[j-1])
//到现在为止已经加了两个数
int m=j+1;//m从左边扫描
int n=num.length-1;//n从右边扫描
while(m&n){//m n扫描数组
sum=num[i]+num[j]+num[m]+num[n];
if(m!=j+1&&num[m]==num[m-1])
else if(n!=num.length-1&&num[n]==num[n+1])
else if(target&sum)
else if(target&sum)
else if(target==sum){//符合条件加到arraylist
ArrayList&Integer& list=new ArrayList &Integer&();
list.add(num[i]);
list.add(num[j]);
list.add(num[m]);
list.add(num[n]);
Collections.sort(list);
arrayList.add(list);
return arrayL
此算法参考了，不过他是用C++实现，其思想是一样的。
阅读(...) 评论()

我要回帖

更多关于 20以内填空加减法 的文章

 

随机推荐