leetcode: 2Sum/3Sum/3SumClosest/4Sum系列问题

leetcode(http://leetcode.com/onlinejudge)上有好几道关于数组中几个数据和为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. public class ThreeSumSolution2 {
  4.     private ArrayList<ArrayList<Integer>> list;
  5.     public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
  6.         list = new ArrayList<ArrayList<Integer>>();
  7.         Arrays.sort(num);
  8.         int i = 0;
  9.         for (i = 0; i <= num.length – 3; i++) {
  10.             if (i != 0 && num[i] == num[i – 1]) {
  11.                 continue;
  12.             }
  13.             judgeAndPut(num, i, i + 1, num.length – 1);
  14.         }
  15.         return list;
  16.     }
  17.     private void judgeAndPut(int[] num, int i, int p, int q) {
  18.         while (p < q) {
  19.             if (num[p] + num[q] < -num[i]) {
  20.                 p++;
  21.             } else if (num[p] + num[q] > -num[i]){
  22.                 q–;
  23.             } else if (num[p] + num[q] == -num[i]) {
  24.                 ArrayList<Integer> tmpList = new ArrayList<Integer>();
  25.                 tmpList.add(num[i]);
  26.                 tmpList.add(num[p]);
  27.                 tmpList.add(num[q]);
  28.                 list.add(tmpList);
  29.                 p++;
  30.                 q–;
  31.                 while (p < q && num[p] == num[p – 1]) {
  32.                     p++;
  33.                 }
  34.                 while (p < q && num[q] == num[q + 1]) {
  35.                     q–;
  36.                 }
  37.             }
  38.         }
  39.     }
  40.     public static void main(String[] args) {
  41.         int num[] = {-1,0,1,2,-1,-4};
  42.         System.out.println(new ThreeSumSolution2().threeSum(num));
  43.     }
  44. }

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. public class ThreeSumClosest {
  3.     private int closest;
  4.     private boolean needInit;
  5.     public int threeSumClosest(int[] num, int target) {
  6.         closest = 0;
  7.         needInit = true;
  8.         Arrays.sort(num);
  9.         int i = 0;
  10.         for (i = 0; i <= num.length – 3; i++) {
  11.             if (i != 0 && num[i] == num[i – 1]) {
  12.                 continue;
  13.             }
  14.             judgeAndPut(num, i, i + 1, num.length – 1, target);
  15.         }
  16.         return closest;
  17.     }
  18.     private void judgeAndPut(int[] num, int i, int p, int q, int target) {
  19.         while (p < q) {
  20.             int sum = num[i] + num[p] + num[q];
  21.             if (needInit || Math.abs(sum – target) < Math.abs(closest – target)) {
  22.                 closest = sum;
  23.             }
  24.             needInit = false;
  25.             if (sum <= target) {
  26.                 p++;
  27.                 while (p < q && num[p] == num[p – 1]) {
  28.                     p++;
  29.                 }
  30.             } else if (sum > target){
  31.                 q–;
  32.                 while (p < q && num[q] == num[q + 1]) {
  33.                     q–;
  34.                 }
  35.             }
  36.         }
  37.     }
  38.     public static void main(String[] args) {
  39.         int num[] = {0,1,2};
  40.         System.out.println(new ThreeSumClosest().threeSumClosest(num, 3));
  41.     }
  42. }

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. public class FourSum {
  4.     private ArrayList<ArrayList<Integer>> list;
  5.     public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
  6.         list = new ArrayList<ArrayList<Integer>>();
  7.         Arrays.sort(num);
  8.         int i = 0;
  9.         int j = 0;
  10.         for (i = 0; i <= num.length – 4; i++) {
  11.             if (i != 0 && num[i] == num[i – 1]) {
  12.                 continue;
  13.             }
  14.             for (j = i + 1; j <= num.length – 3; j++) {
  15.                 if (j != i + 1 && num[j] == num[j – 1]) {
  16.                     continue;
  17.                 }
  18.                 judgeAndPut(num, i, j, j + 1, num.length – 1, target);
  19.             }
  20.         }
  21.         return list;
  22.     }
  23.     private void judgeAndPut(int[] num, int i, int j, int p, int q, int target) {
  24.         while (p < q) {
  25.             int sum = num[i] + num[j] + num[p] + num[q];
  26.             if (sum < target) {
  27.                 p++;
  28.             } else if (sum > target){
  29.                 q–;
  30.             } else if (sum == target) {
  31.                 ArrayList<Integer> tmpList = new ArrayList<Integer>();
  32.                 tmpList.add(num[i]);
  33.                 tmpList.add(num[j]);
  34.                 tmpList.add(num[p]);
  35.                 tmpList.add(num[q]);
  36.                 list.add(tmpList);
  37.                 p++;
  38.                 q–;
  39.                 while (p < q && num[p] == num[p – 1]) {
  40.                     p++;
  41.                 }
  42.                 while (p < q && num[q] == num[q + 1]) {
  43.                     q–;
  44.                 }
  45.             }
  46.         }
  47.     }
  48.     public static void main(String[] args) {
  49.         int num[] = {-1,0,1,0,-2,2};
  50.         System.out.println(new FourSum().fourSum(num, 0));
  51.     }
  52. }

via:leetcode: 2Sum/3Sum/3SumClosest/4Sum系列问题 – To be a crazy and happy coder! – 博客频道 – CSDN.NET.

  • 浏览:540
  • 评论:0

发表新的回复