首页 > 代码库 > leetcode: 2Sum/3Sum/3SumClosest/4Sum系列问题(转载)

leetcode: 2Sum/3Sum/3SumClosest/4Sum系列问题(转载)

2024-07-07 16:19:59   219人阅读

转载：http://blog.csdn.net/li4951/article/details/8693212

leetcode上有好几道关于数组中几个数据和为target的题目。恰好正在看剑指offer中“和为s的两个数组这章”，据此思想，leetcode上的三道题目都被我解决了。总结一下。

 

1.twoSum:

输入一个递增数组和一个数字s，在数组中查找两个数使得它们的和正好是s。

既然题目中已经提到了“递增数组”,那么肯定不会暴力了。因此肯定有<O(n*n)的办法了。

算法：最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数字往后移动；当相等时，打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。

链接：http://zhedahht.blog.163.com/blog/static/2541117420072143251809/

2.threeSum: 

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
  • The solution set must not contain duplicate triplets.
有了twoSum的启发，threeSum所有做的事，只需加上排序，和一层循环。经测试AC。
 
 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 
 4 public class ThreeSumSolution2 {
 5     private ArrayList<ArrayList<Integer>> list;
 6     
 7     public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
 8         list = new ArrayList<ArrayList<Integer>>();
 9         Arrays.sort(num);
10         
11         int i = 0;
12         for (i = 0; i <= num.length - 3; i++) {
13             if (i != 0 && num[i] == num[i - 1]) {
14                 continue;
15             }
16             judgeAndPut(num, i, i + 1, num.length - 1);
17         }
18        
19         return list;
20     }
21 
22     private void judgeAndPut(int[] num, int i, int p, int q) {
23         while (p < q) {
24             if (num[p] + num[q] < -num[i]) {
25                 p++;
26             } else if (num[p] + num[q] > -num[i]){
27                 q--;
28             } else if (num[p] + num[q] == -num[i]) {
29                 ArrayList<Integer> tmpList = new ArrayList<Integer>();
30                 tmpList.add(num[i]);
31                 tmpList.add(num[p]);
32                 tmpList.add(num[q]);
33                 list.add(tmpList);
34                 p++;
35                 q--;
36                 while (p < q && num[p] == num[p - 1]) {
37                     p++;
38                 }
39                 while (p < q && num[q] == num[q + 1]) {
40                     q--;
41                 }
42             }
43         }
44     }
45     
46     public static void main(String[] args) {
47         int num[] = {-1,0,1,2,-1,-4};
48         System.out.println(new ThreeSumSolution2().threeSum(num));
49     }
50 }

 

3. threeSumClosest: 
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
思路和threeSum几乎一样，只是查找条件有所变化而已。代码更简洁了。
 
 1 import java.util.Arrays;
 2 
 3 public class ThreeSumClosest {
 4     private int closest;
 5     private boolean needInit;
 6     
 7     public int threeSumClosest(int[] num, int target) {
 8         closest = 0;
 9         needInit = true;
10         Arrays.sort(num);
11         
12         int i = 0;
13         for (i = 0; i <= num.length - 3; i++) {
14             if (i != 0 && num[i] == num[i - 1]) {
15                 continue;
16             }
17             judgeAndPut(num, i, i + 1, num.length - 1, target);
18         }
19         return closest;
20     }
21 
22     private void judgeAndPut(int[] num, int i, int p, int q, int target) {
23         
24         while (p < q) {
25             int sum = num[i] + num[p] + num[q];
26             if (needInit || Math.abs(sum - target) < Math.abs(closest - target)) {
27                 closest = sum;
28             }
29             needInit = false;
30             
31             if (sum <= target) {
32                 p++;
33                 while (p < q && num[p] == num[p - 1]) {
34                     p++;
35                 }
36             } else if (sum > target){
37                 q--;
38                 while (p < q && num[q] == num[q + 1]) {
39                     q--;
40                 }
41             }
42         }
43         
44     }
45     
46     public static void main(String[] args) {
47         int num[] = {0,1,2};
48         System.out.println(new ThreeSumClosest().threeSumClosest(num, 3));
49     }
50 }

 

 
4. fourSum: 

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.
再多两层循环，此时已经是n立方的时间效率了，尝试了一下，居然也AC了。不知道还有没有更高效的算法。
 
 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 
 4 public class FourSum {
 5     private ArrayList<ArrayList<Integer>> list;
 6     
 7     public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
 8         list = new ArrayList<ArrayList<Integer>>();
 9         Arrays.sort(num);
10         
11         int i = 0;
12         int j = 0;
13         for (i = 0; i <= num.length - 4; i++) {
14             if (i != 0 && num[i] == num[i - 1]) {
15                 continue;
16             }
17             
18             for (j = i + 1; j <= num.length - 3; j++) {
19                 if (j != i + 1 && num[j] == num[j - 1]) {
20                     continue;
21                 }
22                 judgeAndPut(num, i, j, j + 1, num.length - 1, target);
23             }
24             
25         }
26        
27         return list;            
28     }
29 
30     private void judgeAndPut(int[] num, int i, int j, int p, int q, int target) {
31         while (p < q) {
32             int sum = num[i] + num[j] + num[p] + num[q];
33             if (sum < target) {
34                 p++;
35             } else if (sum > target){
36                 q--;
37             } else if (sum == target) {
38                 ArrayList<Integer> tmpList = new ArrayList<Integer>();
39                 tmpList.add(num[i]);
40                 tmpList.add(num[j]);
41                 tmpList.add(num[p]);
42                 tmpList.add(num[q]);
43                 list.add(tmpList);
44                 p++;
45                 q--;
46                 while (p < q && num[p] == num[p - 1]) {
47                     p++;
48                 }
49                 while (p < q && num[q] == num[q + 1]) {
50                     q--;
51                 }
52             }
53         }
54         
55     }
56     
57     public static void main(String[] args) {
58         int num[] = {-1,0,1,0,-2,2};
59         System.out.println(new FourSum().fourSum(num, 0));
60 
61     }
62 
63 }

 

 转载：http://blog.csdn.net/li4951/article/details/8693212


联系
我们