首页 > 代码库 > 4Sum
4Sum
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很像，所以我直接在3sum外面套了一层循环，开始以为会超时来着，因为时间复杂度为O(N^2*logn)但还是没超
开始用四重循环，穷举直接超时了，优化了一下也超时，就用的上面的方法1 import java.util.ArrayList; 2 import java.util.Arrays; 3 import java.util.List; 4 5 6 7 8 9 //class ListNode {10 // public int val;11 // public ListNode next;12 // ListNode(int x) {13 // val = x;14 // next = null;15 // }16 // }17 18 public class Solution {19 public List<List<Integer>> fourSum(int[] num, int target) {20 List<List<Integer>> result = new ArrayList<List<Integer>>();21 Arrays.sort(num); //将数组升序排序22 23 for(int q = 0; q < num.length;q++){24 if(q > 0 && num[q] == num[q - 1])25 continue;26 for(int i = q + 1; i < num.length; i++){27 if(i > q + 1 && num[i] == num[i - 1])28 continue; //去重29 int j = i + 1;30 int k = num.length - 1;31 while(j < k){ //从i + 1 ~ n - 1中找出两个数等于-num[i]32 if(j > i + 1 && num[j] == num[j - 1])33 {34 j++;35 continue;36 }37 if(k < num.length - 1 && num[k] == num[k + 1]){38 k--;39 continue;40 } //去重41 int temp = num[i] + num[j] + num[k] + num[q];42 if(temp > target){ //结果比0大k前移43 k--;44 continue;45 }46 else if(temp < target){47 j++;48 continue;49 }else{ //找到一个解50 List<Integer> element = new ArrayList<Integer>();51 element.add(num[q]);52 element.add(num[i]);53 element.add(num[j]);54 element.add(num[k]);55 result.add(element);56 j++;57 //break; //退出循环58 }59 60 }61 }62 }63 64 65 66 return result;67 }68 }
4Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。