美文网首页
Algorithm-4Sum

Algorithm-4Sum

作者: cctoken | 来源:发表于2019-05-19 20:07 被阅读0次

Algorithm Four Sum

Description

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note
The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [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]

]

Submission

package com.cctoken.algorithm;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author chenchao
 */
public class FourSum {

  public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> finalRes = new LinkedList<List<Integer>>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 3; i++) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }
      int target1 = target - nums[i];
      for (int j = i + 1; j < nums.length - 2; ++j) {
        if (j > i + 1 && nums[j] == nums[j - 1]) {
          continue;
        }
        int target2 = target1 - nums[j];
        int k = j + 1;
        int m = nums.length - 1;
        while (k < m) {
          if (nums[k] + nums[m] < target2) {
            k++;
            while (k < m && nums[k] == nums[k - 1]) {
              k++;
            }
          } else if (nums[k] + nums[m] > target2) {
            m--;
            while (k < m && nums[m] == nums[m + 1]) {
              m--;
            }
          } else {
            List<Integer> res = new LinkedList<Integer>();
            res.add(nums[i]);
            res.add(nums[j]);
            res.add(nums[k]);
            res.add(nums[m]);
            finalRes.add(res);
            k++;
            while (k < m && nums[k] == nums[k - 1]) {
              k++;
            }
            m--;
            while(k < m && nums[m] == nums[m + 1]) {
              m--;
            }
          }
        }
      }
    }
    return finalRes;
  }

  public static void main(String[] args) {
//    int[] nums = new int[]{1, 0, -1, 0, -2, 2};
    int[] nums = new int[]{0, 0, 0, 0};
    int target = 1;
    new FourSum().fourSum(nums, target);

  }
}

Solution

解题思路,参考之前的3个数求和

image.png

相关文章

  • Algorithm-4Sum

    Algorithm Four Sum Description Given an array nums of n i...

网友评论

      本文标题:Algorithm-4Sum

      本文链接:https://www.haomeiwen.com/subject/kgoqzqtx.html