最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

18. 4Sum

XAMPP相关 admin 189浏览 0评论

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]
]
难度:medium

题目:
给定一整数数组和一目标整数,是否存在4个数的和为指定整数? 找出所有这样不同的4元组。
注意:
答案一定不能包含重复的四元组。

思路:
数组排序,固定一个数,然后降级为3sum

Runtime: 34 ms, faster than 78.86% of Java online submissions for 4Sum.
Memory Usage: 31.7 MB, less than 13.82% of Java online submissions for 4Sum.

class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList();
Arrays.sort(nums);
int numsLen = nums.length;
for (int k = 0; k < numsLen; k++) {
if (0 == k || nums[k - 1] != nums[k]) {
for (int i = k + 1; i < numsLen; i++) {
if ((k + 1) == i || nums[i - 1] != nums[i]) {
for (int left = i + 1, right = numsLen – 1; left < right; left++, right–) {
int sum = nums[left] + nums[right] + nums[i] + nums[k];
if (target == sum
&& ((i + 1) == left || nums[left - 1] != nums[left])
&& ((numsLen – 1) == right || nums[right] != nums[right + 1])
) {
result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
} else if (sum > target) {
left–;
} else {
right++;
}
}
}
}
}
}

return result;
}
}

转载请注明:XAMPP中文组官网 » 18. 4Sum