首页 > 代码库 > [leetcode]4Sum

[leetcode]4Sum

2024-07-11 22:33:22   220人阅读

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：
与之前的[leetcode]3Sum类似，加一层外部循环，时间复杂度为O(n ^ 3)
代码如下：
 1 public class Solution { 2     public List<List<Integer>> fourSum(int[] num, int target) { 3         List<List<Integer>> result = new ArrayList<List<Integer>>(); 4         if(num == null || num.length < 4) return result; 5         int length = num.length; 6         Arrays.sort(num); 7         for (int i = 0; i < length - 3; i++) { 8             if(i > 0 && num[i] == num[i - 1])continue; 9             int one = i;10             for (int j = i + 1; j < length - 2; j++) {11                 if(j > i + 1 && num[j] == num[j - 1])continue;12                 int two = j;13                 int three = j + 1;14                 int four = length - 1;15                 while (three < four) {16                     int sum = num[one] + num[two] + num[three] + num[four];17                     if(sum < target) three++;18                     else if(sum > target) four--;19                     else{20                         List<Integer> list = new ArrayList<Integer>();21                         list.add(num[one]);22                         list.add(num[two]);23                         list.add(num[three]);24                         list.add(num[four]);25                         result.add(list);26                         three++;27                         four--;28                     while(three < four && num[three] == num[three-1]) three++;29                         while(three < four &&num[four] == num[four+1]) four--;30                     }31                 }32             }33         }34         return result;35     }36 }

【吐槽】第一次做这道题的时候，怎么也想不到O(n ^ 3)居然能过，绞尽乳汁【(⊙o⊙)好邪恶】想怎么才能把时间复杂度压缩到O(n ^ 2)，我相信面试的时候要求肯定也是O(n^2)，因此查了网上的一些大神的思路，对本题做了进一步的优化

思路2:

1. 计算出数组中两两元素的和，把这种二度元素成为nodeOfTwo（学过排列组合的话，应该可以想象到这个数有多大，没办法，空间换时间吧）

2. 对每一个nodeOfTwo元素进行遍历，类似于求[leetcode]Two Sum

2.1 如果存在两个nodeOfTwo元素的和为target，即找到了满足条件的四个元素。

2.2 nodeOfTwo的value毫无疑问是一个list

疑问：

1. 如何去除相同元素？对于nodeOfTwo - 3【何为3的元素对组合】中可能包含两对或以上（0,3）

2. 如何去除重复元素？对于不同的nodeOfTwo节点的组合，还可能有重复，例如nodeOfTwo - 1 和nodeOfTwo - 4包含一个组合（0，1，1，3）但是nodeOfTwo - 3 和nodeOfTwo - 2 中可能包含（0,3,1,1）事实上是重复元素。

代码如下：

 

 1 public List<List<Integer>> fourSum(int[] num, int target) { 2         List<List<Integer>> result = new ArrayList<List<Integer>>(); 3         if(num == null || num.length < 4) return result; 4         int length = num.length; 5         Arrays.sort(num); 6         Map<Integer,List<int[]>> hash = new HashMap<Integer,List<int[]>>(); 7         for(int i = 0; i < length - 1;i++){ 8             for(int j = i + 1; j < length; j++){ 9                 int sum = num[i] + num[j];10                 if(hash.get(sum) == null){11                     List<int[]> list = new ArrayList<int[]>();12                     list.add(new int[]{i,j});13                     hash.put(sum, list);14                 }else{15                     hash.get(sum).add(new int[]{i,j});16                 }17             }18         }19         for(int nodeOfTwo : hash.keySet()){20             if(hash.containsKey(target - nodeOfTwo)){21                 for(int[] oneAndTwo : hash.get(nodeOfTwo)){22                     for(int[] threeAndFour : hash.get(target - nodeOfTwo)){23                         if(oneAndTwo[0] == threeAndFour[0] || oneAndTwo[0] == threeAndFour[1] || oneAndTwo[1] == threeAndFour[0] || oneAndTwo[1] == threeAndFour[1] )continue;//去除重复元素24                         int[] node = {num[oneAndTwo[0]],num[oneAndTwo[1]],num[threeAndFour[0]],num[threeAndFour[1]]};25                         Arrays.sort(node);26                         boolean exist = false;27                         for(List<Integer> tem : result){//去除相同元素28                             int count = 0;29                             for(int i = 0; i < 4; i++){30                                 if(node[i] == tem.get(i))count++;31                             }32                             if(count == 4) exist = true;33                         }34                         if(!exist) {35                             List<Integer> list = new ArrayList<Integer>();36                             for(int i = 0; i < 4; list.add(node[i++]));37                             result.add(list);38                         }39                     }40                 }41             }42         }43         return result;44     }

【吐槽】代码还是太丑了，哎，不过与之前的相比还是稍微好点的，慎重点击->[leetcode]4Sum


联系
我们