1. 两数之和
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) return new int[]{map.get(target - nums[i]), i};
map.put(nums[i], i);
}
return new int[2];
}
}
顺便把3Sum, 4Sum也总结了.
15. 三数之和
实际上就是在确定一个值的基础上再做twoSum, 我这里改为了用双指针来做. 两个方法都要跳过连续的相同值, 目的是去重. 题目要求是和为0, 但实际上其他target也可以.
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int index = 0;
for (int i = 0; i < nums.length - 2; i++) {
twoSum(nums, i + 1, 0 - nums[i]);
while (i + 1 < nums.length - 2 && nums[i] == nums[i + 1]) i++;
}
return res;
}
public void twoSum(int[] nums, int l, int target) {
int left = l, right = nums.length - 1;
while (left < right) {
int a = nums[left], b = nums[right];
if (a + b == target) {
res.add(new ArrayList<Integer>(Arrays.asList(nums[l - 1], a, b))); //减一才是已经选择的那个数字
while (left < right && nums[left] == a) left++;
while (left < right && nums[right] == b) right--;
} else if (a + b < target) {
while (left < right && nums[left] == a) left++;
} else {
while (left < right && nums[right] == b) right--;
}
}
}
}
18. 四数之和
在threeSum的基础上再加一层. 这里可以找到规律, 对于nSum问题, 底层永远都是双指针, 所以只要不段递归求解即可, 只要n最后减到2, 就可以返回答案.
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
threeSum(nums, i + 1, target - nums[i]);
while (i + 1 < nums.length - 3 && nums[i] == nums[i + 1]) i++;
}
return res;
}
public void threeSum(int[] nums, int left0, int target) {
for (int i = left0; i < nums.length - 2; i++) {
twoSum(nums, left0, i + 1, target - nums[i]);
while (i + 1 < nums.length - 2 && nums[i] == nums[i + 1]) i++;
}
}
public void twoSum(int[] nums, int left0, int left1, int target) {
int left = left1, right = nums.length - 1;
while (left < right) {
int a = nums[left], b = nums[right];
if (a + b == target) {
res.add(new ArrayList<Integer>(Arrays.asList(nums[left0 - 1], nums[left1 - 1], a, b)));
while (left < right && nums[left] == a) left++;
while (left < right && nums[right] == b) right--;
} else if (a + b < target) {
while (left < right && nums[left] == a) left++;
} else {
while (left < right && nums[right] == b) right--;
}
}
}
}
参考
comments powered by Disqus