Solve by using TreeSet instead of map to find the max sum under K.
public int twoSumLessThanK(int[] A, int K) {
TreeSet<Integer> set = new TreeSet<>();
int max = Integer.MIN_VALUE;
for (int i = 0; i < A.length; i++) {
if (set.lower(K - A[i]) != null) {
max = Math.max(max, set.lower(K - A[i]) + A[i]);
}
set.add(A[i]);
}
return max == Integer.MIN_VALUE ? -1 : max;
}
Use if (i > 0 && nums[i] == nums[i - 1]) continue and while (left < right && nums[left] == nums[left + 1]) left++ etc to remove duplicates.
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 2) return new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int target = -nums[i];
int left = i + 1, right = n - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
result.add(Arrays.asList(nums[i], 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 (left < right && nums[left] + nums[right] < target) {
left++;
} else if (left < right && nums[left] + nums[right] > target) {
right--;
}
}
}
return result;
}
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 2) return -1;
Arrays.sort(nums);
int n = nums.length;
Integer res = null;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (res == null || Math.abs(sum - target) < Math.abs(res - target)) {
res = sum;
}
if (left < right && sum < target) {
left++;
} else {
right--;
}
}
}
return res;
}
public int threeSumSmaller(int[] nums, int target) {
int count = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] < target) {
count += right - left;
left++;
} else {
right--;
}
}
}
return count;
}
Given a sorted list of numbers and a target Z, return the number of pairs according to following definition: (X,Y) where X+Y >= Z
Example 1:
Input: arr = [1, 3, 7, 9, 10, 11], Z = 7
Output: 14
public static int numOfSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int count = 0;
while (left < right) {
if (nums[left] + nums[right] >= target) {
count += right - left;
right--;
} else {
left++;
}
}
return count;
}
18. 4Sum
170. Two Sum III - Data structure design
653. Two Sum IV - Input is a BST
4Sum / kSum
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return kSum(nums, 0, 4, target);
}
private List<List<Integer>> kSum (int[] nums, int start, int k, int target) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(k == 2) { //two pointers from left and right
int left = start, right = len - 1;
while(left < right) {
int sum = nums[left] + nums[right];
if(sum == target) {
List<Integer> path = new ArrayList<Integer>();
path.add(nums[left]);
path.add(nums[right]);
res.add(path);
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) { //move left
left++;
} else { //move right
right--;
}
}
} else {
for(int i = start; i < len - (k - 1); i++) {
if(i > start && nums[i] == nums[i - 1]) continue;
List<List<Integer>> temp = kSum(nums, i + 1, k - 1, target - nums[i]);
for(List<Integer> t : temp) {
t.add(0, nums[i]);
}
res.addAll(temp);
}
}
return res;
}