首页 > 代码库 > 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)
1 public class Solution { 2 public List<List<Integer>> fourSum(int[] num, int target) { 3 List<List<Integer>> ret = new ArrayList<List<Integer>>(); 4 if (num==null||num.length<4) return ret; 5 int n=num.length; 6 Arrays.sort(num); 7 int i,j,start,end,sum; 8 for (i = 0; i < n-3; i++) { 9 for (j = i+1; j <n-2 ; j++) {10 start=j+1;11 end=n-1;12 while (start < end) {13 sum = num[start] + num[end];14 if (sum < target - num[i] - num[j]) {15 start++;16 }else if (sum > target - num[i] - num[j]) {17 end--;18 } else {19 ArrayList<Integer> list = new ArrayList<Integer>();20 list.add(num[i]);21 list.add(num[j]);22 list.add(num[start]);23 list.add(num[end]);24 ret.add(list);25 start++;26 end--;27 while(end>start && num[start-1]==num[start])++start;28 while (end>start && num[end+1]==num[end]) --end;29 }30 }31 while (j<n-1&&num[j]==num[j+1]) ++j;32 33 }34 while (i<n-1&&num[i]==num[i+1]) ++i;35 }36 return ret;37 }38 }
LeetCode 4Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。