四刷 06/2022
Version #1 Two Pointers
一个可以优化但是没写出来的点就是因为array是sorted，所以如果outer loop的nums[i] > 0就可以break了，因为三个 >0 的数是没法加成0的
这里犯了一个错误就是
Arrays.asList(new int[]{a, b})这样创造出来的ArrayList是immutable的，如果想让它mutable就要先赋值给一个 new ArrayList<>(Arrays.asList(a, b))
同时看了之前的写法，也可以直接把result list的reference传进去，然后2sum找到结果以后直接加到结果里面
Time O(N^2)
Space O(logN) to O(N) used by the sorting algorithm
Runtime: 37 ms, faster than 46.23% of Java online submissions for 3Sum.
Memory Usage: 59.8 MB, less than 32.09% of Java online submissions for 3Sum.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
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;
}
List<List<Integer>> pairs = twoSum(nums, i + 1, nums.length - 1, -nums[i]);
for (List<Integer> pair : pairs) {
pair.add(nums[i]);
result.add(pair);
}
}
return result;
}
// Find distinct pair that add up to target from nums[start, end]
private List<List<Integer>> twoSum(int[] nums, int start, int end, int target) {
List<List<Integer>> result = new ArrayList<>();
while (start < end) {
int sum = nums[start] + nums[end];
if (sum == target) {
result.add(new ArrayList<>(Arrays.asList(nums[start], nums[end])));
start++;
while (start < end && nums[start] == nums[start - 1]) {
start++;
}
} else if (sum < target) {
start++;
} else {
end--;
}
}
return result;
}
}
Version #2 HashSet - no sorting
Time O(N^2)
Space O(N)
Runtime: 684 ms, faster than 14.39% of Java online submissions for 3Sum.
Memory Usage: 150.5 MB, less than 6.74% of Java online submissions for 3Sum.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
Set<Integer> visited = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (visited.contains(nums[i])) {
continue;
}
visited.add(nums[i]);
Set<Integer> seen = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
if (seen.contains(-nums[i] - nums[j])) {
List<Integer> tuple = Arrays.asList(nums[i], nums[j], -nums[i] - nums[j]);
Collections.sort(tuple);
result.add(tuple);
}
seen.add(nums[j]);
}
}
return new ArrayList<>(result);
}
}
Output:[[0,0,0],[0,0,0]]
Expected:[[0,0,0]]
三刷 05/2022
一遍bug free过了，开心
重点是要通过sorted array 来deduplicate
这里稍微陷入了一个错误，就是以为如果 i, j, k在sorted array里面，那一定只能是两个小的值加起来得到一个大的值。其实这是不对的
nums[i] + nums[j] + nums[k] = 0，无论把哪个数放到右边都成立
所以outer loop不一定是i = nums.length - 1, i--，如果用i = 0, i < nums.length也是正确的
Runtime: 25 ms, faster than 82.71% of Java online submissions for 3Sum.
Memory Usage: 58.7 MB, less than 59.10% of Java online submissions for 3Sum.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// Make it a two sum question
// nums[i] + nums[j] == nums[k]
// Since we want to deduplicate the solution set, we need to sort the array first and skip numbers when index != 0 && nums[index] == nums[index - 1]
if (nums == null || nums.length < 2) {
return new ArrayList<>();
}
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = nums.length - 1; i >= 0; i--) {
if (i != nums.length - 1 && nums[i] == nums[i + 1]) {
continue;
}
twoSum(nums, i, result);
}
return result;
}
// Given nums[startIndex], find all pairs of numbers on its left that sum up to its value
private void twoSum(int[] nums, int endIndex, List<List<Integer>> result) {
int target = -nums[endIndex];
int left = 0, right = endIndex - 1;
while (left < right) {
if (nums[left] + nums[right] < target) {
left++;
continue;
}
if (nums[left] + nums[right] > target) {
right--;
continue;
}
result.add(Arrays.asList(nums[left], nums[right], nums[endIndex]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
}
二刷
还是写的很艰难
对于一样的数的处理是跳过，left不能和left+1一样，right不能和right-1一样，但是left是可以和right一样的
有空还是再写写吧
result.add(Arrays.asList(nums[targetIndex], nums[left], nums[right]));
这种写法也要熟悉
79.71 %
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length <= 2) return result;
Arrays.sort(nums);
//TODO
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || nums[i] != nums[i - 1]) {
twoSum(nums, i, result);
}
}
return result;
}
private void twoSum(int[] nums, int targetIndex, List<List<Integer>> result) {
int target = 0 - nums[targetIndex];
int left = targetIndex + 1, right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
result.add(Arrays.asList(nums[targetIndex], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (nums[left] + nums[right] > target) {
right--;
} else {
left++;
}
}
}
}
Version #1 Two Pointers
Time O(n^2)
三刷
三个数当遇到duplicate的时候都要跳
36.43 %
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 3) {
return result;
}
Arrays.sort(nums);
int len = nums.length;
for (int i = 0; i < len; i++) {
if (i != 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = len - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum < 0) {
left++;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
} else {
right--;
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
}
return result;
}
}
一刷
Given an array S of n integers, are there elements a, b, c in S such that
a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Notice
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
做这道题出现了很多小bug，主要问题是在用pointer的时候，while loop是不能无脑加的
每一次都要判断pointer是否出界
判断依据譬如left < right, index > 0, index < numbers.length等等
TwoSum可以单独写成一个method
Time Complexity O(n^2) Space Complexity O(1)
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
Arrays.sort(nums);
int left, right;
int index = 0;
while (index < nums.length - 2) {
if (index > 0 && nums[index] == nums[index - 1]) {
index++;
continue;
}
int target = nums[index];
left = index + 1;
right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] + target == 0) {
List<Integer> temp = new ArrayList<>();
temp.add(target);
temp.add(nums[left]);
temp.add(nums[right]);
result.add(temp);
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (nums[left] + nums[right] + target < 0) {
left++;
} else {
right--;
}
}
index++;
}
return result;
}
}
No comments:
Post a Comment