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)


      

1 package com.rust.cal;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Arrays;
 5 import java.util.List;
 6 
 7 public class FourSum {
 8     
 9     public static List<List<Integer>> fourSum(int[] nums, int target) {
10         List<List<Integer>> res = new ArrayList<List<Integer>>();
11         Arrays.sort(nums);
12         int len = nums.length;
13         for (int i = 0; i < len - 3; i++) {
14             if (i > 0 && nums[i] == nums[i-1])    continue;
15             for (int j = len - 1; j > i + 2; j--) {
16                 if (j < len - 1 && nums[j] == nums[j+1])    continue;
17                 int side = nums[i] + nums[j];
18                 int left = i + 1;
19                 int right = j - 1;
20                 while (left < right) {
21                     int inner = nums[left] + nums[right];
22                     if (side + inner == target) {
23                         List<Integer> singleAns = new ArrayList<Integer>();
24                         singleAns.add(nums[i]);
25                         singleAns.add(nums[left]);
26                         singleAns.add(nums[right]);
27                         singleAns.add(nums[j]);
28                         res.add(singleAns);
29                         while (left < right && nums[left] == nums[left+1]) left++;  //look forward
30                         while (left < right && nums[right] == nums[right-1]) right--;   //skip the same number in nums[]
31                         left++;
32                         right--;
33                     } else if (inner + side > target){
34                         right--;
35                     } else {
36                         left++;
37                     }
38                 }
39             }
40         }
41         return res;
42     }
43 
44     public static void main(String args[]){
45         List<List<Integer>> res = new ArrayList<List<Integer>>();
46         int[] nums = {-5,5,4,-3,0,0,4,-2};
47         int target = 4;
48         res = fourSum(nums, target);
49         /*output*/
50         for (int i = 0; i < nums.length; i++) {
51             System.out.print(nums[i] + " ");
52         }
53         System.out.println();
54         System.out.println(res.size());
55         for (int i = 0; i < res.size(); i++) {
56             for (int j = 0; j < res.get(i).size(); j++) {
57                 System.out.print(res.get(i).get(j) + "\t");
58             }
59             System.out.println();
60         }
61     }
62 
63 }