首页 > 代码库 > leetcode 4Sum
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:
- 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)
类似3Sum方法，只是在外层多加一个for循环，但是对于去重的控制边界条件需要注意，这里的while中n的判断下线为j+11 package si.Sum; 2 3 import java.util.ArrayList; 4 import java.util.Arrays; 5 import java.util.List; 6 7 public class SiSum { 8 public static void main(String args[]){ 9 //int num[]={2,1,0,-1};10 int num[]={-1,0,-5,-2,-2,-4,0,1,-2};11 List<List<Integer>> list=fourSum(num, -9);12 for(List<Integer> temp:list){13 for(int i:temp){14 System.out.print(i+"-->");15 }16 System.out.println();17 }18 }19 public static List<List<Integer>> fourSum(int[] num, int target) {20 Arrays.sort(num);21 int len=num.length;22 List<List<Integer>> list=new ArrayList<List<Integer>>();23 for(int i=0;i<=len-4;i++){24 for(int j=i+1;j<=len-3;j++){25 int m=j+1;26 int n=len-1;27 int diff=(target-num[i]-num[j]);28 while(m<n){29 int twoSum=num[m]+num[n];30 if(twoSum>diff){31 n--;32 }else if(twoSum<diff){33 m++;34 }else{35 List<Integer> tempList=new ArrayList<Integer>();36 tempList.add(num[i]);37 tempList.add(num[j]);38 tempList.add(num[m]);39 tempList.add(num[n]);40 list.add(tempList);41 n--;42 m++;43 while(m<len-1&&num[m]==num[m-1])44 {45 m++;46 }47 while(n>=j+1&&n<len-1&&num[n]==num[n+1]){48 n--;49 }50 }51 }52 while(j<len-1&&num[j+1]==num[j]){53 j++;54 }55 }56 while(i<len-1&&num[i+1]==num[i]){57 i++;58 }59 }60 return list; 61 }62 }
leetcode 4Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。