二刷 06/2022
Version #2 K Sum
Time O(N^(k - 1))
Space O(k) for recursion
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return kSum(nums, 0, (long)target, 4);
}
// Calculates k sum for subarray [start, len)
private List<List<Integer>> kSum(int[] nums, int start, long target, int k) {
if (k ==2) {
return twoSum(nums, start, target);
}
List<List<Integer>> result = new ArrayList<>();
for (int i = start; i < nums.length; i++) {
if (i != start && nums[i] == nums[i - 1]) {
continue;
}
for (List<Integer> sub : kSum(nums, i + 1, target - nums[i], k - 1)) {
sub.add(nums[i]);
result.add(sub);
}
}
return result;
}
private List<List<Integer>> twoSum(int[] nums, int start, long target) {
List<List<Integer>> result = new ArrayList<>();
int end = nums.length - 1;
while (start < end) {
int sum = nums[start] + nums[end];
if (sum < target) {
start++;
} else if(sum > target) {
end--;
} else {
result.add(new ArrayList<>(Arrays.asList(nums[start], nums[end])));
start++;
while (start < end && nums[start] == nums[start - 1]) {
start++;
}
}
}
return result;
}
}
Version #1 Two Pointers
比上次做这个题多了一个testcse
[1000000000,1000000000,1000000000,1000000000]
-294967296
这里target - nums[i] - nums[j] 会负数overflow的
加了一个cast成long的操作 long sum = (long)target - (first + second);
Time O(N^3)
Space O(1)
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
twoSum(nums, target, nums[i], nums[j], j + 1, result);
}
}
return result;
}
private void twoSum(int[] nums, int target, int first, int second, int startIndex, List<List<Integer>> result) {
long sum = (long)target - (first + second);
int start = startIndex, end = nums.length - 1;
while (start < end) {
if (nums[start] + nums[end] <= sum) {
// System.out.printf("nums[%d]+nums[%d]=%d\n", start, end, nums[start] + nums[end]);
if (nums[start] + nums[end] == sum && (start == startIndex || nums[start] != nums[start - 1])) {
result.add(Arrays.asList(first, second, nums[start], nums[end]));
}
start++;
} else {
end--;
}
}
}
}
一刷
Version #1 Two Pointers
Time O(n^3)
Space O(1)
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
// Assuming a < b < c < d
// nums[a] + nums[b] + nums[c] + nums[d] == target
// nums[c] + nums[d] = target - (nums[a] + nums[b])
// For each combination of (a, b), try to find nums[c] and nums[d] that satisfy this criteria
if (nums == null || nums.length < 4) {
return new ArrayList<>();
}
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
twoSum(nums, target, i, j, result);
}
}
return result;
}
private void twoSum(int[] nums, int target, int i, int j, List<List<Integer>> result) {
int sum = target - nums[i] - nums[j];
// Find pairs from [j + 1, nums.length] that sum up to the sum value
int start = j + 1;
int end = nums.length - 1;
while (start < end) {
if (nums[start] + nums[end] > sum) {
end--;
continue;
}
if (nums[start] + nums[end] < sum) {
start++;
continue;
}
result.add(Arrays.asList(nums[i], nums[j], nums[start], nums[end]));
start++;
while (start < end && nums[start] == nums[start - 1]) {
start++;
}
}
}
}
Version #2 HashMap version (with extra O(n) space)
Time O(n^3)
Space O(n)
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums == null || nums.length < 4) {
return new ArrayList<>();
}
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
result.addAll(twoSum(nums, target, i, j));
}
}
return result;
}
private List<List<Integer>> twoSum(int[] nums, int target, int i, int j) {
Set<Integer> expected = new HashSet<>();
List<List<Integer>> res = new ArrayList<>();
for (int k = j + 1; k < nums.length; k++) {
// If a number has been added to the result as the last number, skip it
if (!res.isEmpty() && res.get(res.size() - 1).get(3) == nums[k]) {
continue;
}
if (expected.contains(nums[k])) {
res.add(Arrays.asList(nums[i], nums[j], target - nums[i] - nums[j] - nums[k], nums[k]));
}
expected.add(target - nums[i] - nums[j] - nums[k]);
}
return res;
}
}
No comments:
Post a Comment