Leetcode 18.4Sum

本文主要是介绍Leetcode 18.4Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

@author stormma
@date 2017/11/03

---

生命不息，奋斗不止！

---

题目

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: 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]
]

思路分析

在3sum基础上，再加一次循环即可，可以增加剪枝来换取运行时间，
时间复杂度O(N^3)

代码实现

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ans = new ArrayList<>();if (nums.length < 4) {return ans;}Arrays.sort(nums);if (4 * nums[0] > target || 4 * nums[nums.length - 1] < target) {return ans;}int max = nums[nums.length - 1];// -2 -1 0 0 1 2for (int i = 0; i < nums.length - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if (4 * nums[i] > target) {break;}// 剪枝if (nums[i] + 3 * max < target) {continue;}for (int j = i + 1; j < nums.length - 2; j++) {// 3// -4 -3 0 5 5 10int low = j + 1, high = nums.length - 1, goal = target - nums[i] - nums[j];// 剪枝if (nums[i] + nums[j] + 2 * max < target) {continue;}// 去重if (j > i + 1 && nums[j - 1] == nums[j]) {continue;}while (low < high) {if (nums[low] + nums[high] < goal) {low++;} else if (nums[low] + nums[high] > goal) {high--;} else {ans.add(Arrays.asList(nums[i], nums[j], nums[low], nums[high]));while (low < high && nums[low + 1] == nums[low]) {low++;}while (low < high && nums[high - 1] == nums[high]) {high--;}low++;high--;}}}}return ans;}}

这篇关于Leetcode 18.4Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---