一刷 06/2022
Version #1 Two Pointers
As a quick refresher, the pointers are initially set to the first and the last element respectively. We compare the sum of these two elements with the target. If it is smaller than the target, we increment the lower pointer left. Otherwise, we decrement the higher pointer right. Thus, the sum always moves toward the target, and we "prune" pairs that would move it further away. Again, this works only if the array is sorted.
Time O(NlogN)
Space O(logN) to O(N) depends on the sorting algorithm
class Solution {
public int twoSumLessThanK(int[] nums, int k) {
int max = -1;
Arrays.sort(nums);
int start = 0, end = nums.length - 1;
while (start < end) {
if (nums[start] + nums[end] < k) {
max = Math.max(max, nums[start] + nums[end]);
start++;
} else {
end--;
}
}
return max;
}
}
Version #2 Counting Sort + Two Pointers
有一个很容易错的点就是当start==end的时候也是有可能的，要求count[start] > 1这样就可以同样的数加在一起
Time O(M + N) - M is the range of values in the input array, N is the length of the input array
Space O(M)
class Solution {
public int twoSumLessThanK(int[] nums, int k) {
int[] count = new int[1001];
for (int num : nums) {
count[num]++;
}
int max = -1;
int start = 0, end = count.length - 1;
while (start <= end) {
if (count[start] == 0) {
start++;
continue;
}
if (count[end] == 0) {
end--;
continue;
}
if (start + end >= k) {
end--;
continue;
}
// start + end < k
if (start < end || count[start] > 1) {
max = Math.max(max, start + end);
}
start++;
}
return max;
}
}
No comments:
Post a Comment