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≤da \leq b \leq c \leq da≤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. (-1,  0, 0, 1)
  2. (-2, -1, 1, 2)
  3. (-2,  0, 0, 2)

分析

先排序，然后左右夹逼，复杂度 O(n3)O(n^3)，会超时。

可以用一个hashmap先缓存两个数的和，最终复杂度O(n3)O(n^3)。这个策略也适用于 3Sum 。

左右夹逼

  1. // 4Sum
  2. // 先排序，然后左右夹逼
  3. // Time Complexity: O(n^3)，Space Complexity: O(1)
  4. public class Solution {
  5.     public List<List<Integer>> fourSum(int[] nums, int target) {
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         if (nums.length < 4) return result;
  8.         Arrays.sort(nums);
  10.         for (int i = 0; i < nums.length - 3; ++i) {
  11.             if (i > 0 && nums[i] == nums[i-1]) continue;
  12.             for (int j = i + 1; j < nums.length - 2; ++j) {
  13.                 if (j > i+1 && nums[j] == nums[j-1]) continue;
  14.                 int k = j + 1;
  15.                 int l = nums.length - 1;
  16.                 while (k < l) {
  17.                     final int sum = nums[i] + nums[j] + nums[k] + nums[l];
  18.                     if (sum < target) {
  19.                         ++k;
  20.                         while(nums[k] == nums[k-1] && k < l) ++k;
  21.                     } else if (sum > target) {
  22.                         --l;
  23.                         while(nums[l] == nums[l+1] && k < l) --l;
  24.                     } else {
  25.                         result.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
  26.                         ++k;
  27.                         --l;
  28.                         while(nums[k] == nums[k-1] && k < l) ++k;
  29.                         while(nums[l] == nums[l+1] && k < l) --l;
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.         return result;
  35.     }
  36. }

HashMap 做缓存

  1. // 4Sum
  2. // 先排序，然后左右夹逼
  3. // Time Complexity: O(n^3)，Space Complexity: O(1)
  4. public class Solution {
  5.     public List<List<Integer>> fourSum(int[] nums, int target) {
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         if (nums.length < 4) return result;
  8.         Arrays.sort(nums);
  10.         final HashMap<Integer, ArrayList<int[]>> cache = new HashMap<>();
  11.         for (int i = 0; i < nums.length; ++i) {
  12.             for (int j = i + 1; j < nums.length; ++j) {
  13.                 ArrayList<int[]> value = cache.get(nums[i] + nums[j]);
  14.                 if (value == null) {
  15.                     value = new ArrayList<>();
  16.                     cache.put(nums[i] + nums[j], value);
  17.                 }
  18.                 value.add(new int[]{i, j});
  19.             }
  20.         }
  22.         final HashSet<String> used = new HashSet<>(); // avoid duplicates
  23.         for (int i = 0; i < nums.length; ++i) {
  24.             if (i > 0 && nums[i] == nums[i-1]) continue;
  25.             for (int j = i + 1; j < nums.length - 2; ++j) {
  26.                 if (j > i+1 && nums[j] == nums[j-1]) continue;
  27.                 final ArrayList<int[]> list = cache.get(target - nums[i] - nums[j]);
  28.                 if (list == null) continue;;
  29.                 for (int[] pair : list) {
  30.                     if (j >= pair[0]) continue;  // overlap
  32.                     final Integer[] sol = new Integer[]{nums[i], nums[j], nums[pair[0]], nums[pair[1]]};
  33.                     Arrays.sort(sol);
  34.                     final String key = Arrays.toString(sol);
  36.                     if(!used.contains(key)){
  37.                         result.add(Arrays.asList(sol));
  38.                         used.add(key);
  39.                     }
  40.                 }
  41.             }
  42.         }
  43.         return result;
  44.     }
  45. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/4sum.html