2/3/4
除了Two Sum的O(n)解法，其余双指针题目均需先排序。
1. Two Sum
O(n)解法，用HashMap，放入HashMap的时候，key直接做差，这样搜索到这个差的时候，可以直接取出index。
public class Solution {
public int[] twoSum(int[] nums, int target) {
if (nums.length < 2) return new int[2];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
if (map.containsKey(nums[i])) {
int[] res = new int[2];
res[0] = map.get(nums[i]);
res[1] = i;
return res;
} else {
map.put(target - nums[i], i);
}
}
return new int[2];
}
}
167. Two Sum II - Input array is sorted
当然上面那个O(n)解法跟双指针的联系不大，就是一种做法，因为这里双指针的使用环境必须在排序之后的元素中，所以167这道题就是一个小变种，排序数组的two sum，双指针很简单。
public class Solution {
public int[] twoSum(int[] nums, int target) {
Arrays.sort(nums);
int i = 0;
int j = nums.length - 1;
while (i < j) {
int sum = nums[i] + nums[j];
if (sum == target) {
int[] res = new int[2];
res[0] = i + 1;
res[1] = j + 1;
return res;
}
if (sum < target) {
i++;
} else {
j--;
}
}
return new int[2];
}
}
170. Two Sum III - Data structure design
这题跟指针没什么关系，但是既然是two sum相关的，就放在这里了。
这是个典型的 data structure design trade off 问题，因为 add() 和 find() 函数总有一个会很慢，问题在于让哪个慢，就要取决于具体的 workload，真问到这种问题一定要先问清楚。
需要注意的 corner case 是，[add(0), find(0)]，这类情况，还有 [add(2), add(2), find(4)] 这类。
相同的数字再加入显然失去了意义，所以我们用hashset去重。
Quick-Find:
Quick-Find的想法很简单，对于每两个数都求一下和，存到一个hashset中去，因为返回的只需要True/False，所以我们只要判断有没有这样的和就行了。
注意corner case [add(0), find(0)]的处理，要后加number到num set中去。
public class TwoSum {
Set<Integer> num;
Set<Integer> sum;
/** Initialize your data structure here. */
public TwoSum() {
num = new HashSet<>();
sum = new HashSet<>();
}
/** Add the number to an internal data structure.. */
public void add(int number) {
if (num.contains(number)) {
sum.add(number * 2);
} else {
Iterator<Integer> it = num.iterator();
while (it.hasNext()) {
sum.add(it.next() + number);
}
num.add(number);
}
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
return sum.contains(value);
}
}
Quick-Add:
Quick-Add就是先把数都加到一个hashmap中，因为如果同一个数出现了两次，那么结果还是不同的，所以出现次数就只有0，1，2三种可能，当然出现0次的话是不会出现在hashmap中的。Find的时候需要计算。这个出现次数也可以做一点小文章，让速度更快。
事实证明，拿到 iterator 手动 iter.next 要比直接用 enhanced for loop 快。
public class TwoSum {
Map<Integer, Integer> map;
/** Initialize your data structure here. */
public TwoSum() {
map = new HashMap<>();
}
/** Add the number to an internal data structure.. */
public void add(int number) {
if (map.containsKey(number)) {
map.put(number, 2);
} else map.put(number, 1);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
Iterator<Integer> it = map.keySet().iterator();
while (it.hasNext()) {
int key = it.next();
if (map.containsKey(value - key)) {
if (key != value - key || map.get(key) == 2) return true;
}
}
return false;
}
}
15. 3Sum
题目要求：The solution set must not contain duplicate triplets.
这题唯一的问题就是去重，三个指针都要注意一次迭代，同样只加一次，要靠 while 推一下。
if (k != 0 && nums[i] == nums[i - 1]) continue;
跳过重复值，像0，0，0，0。
nums[i] == nums[i - 1]
nums[j] == nums[j + 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);
for (int i = 0; i < nums.length - 2; ++i) {
if (i != 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left++]);
list.add(nums[right--]);
result.add(list);
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
16. 3Sum Closest
一个意思，先排序，不用跳过重复值。用一个变量保存abs最近。
public class Solution {
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 3) return -1;
int curMin = Math.abs(nums[0] + nums[1] + nums[2] - target);
int curSum = nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; ++i) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
return sum;
} else if (sum < target) {
left++;
} else right--;
if (Math.abs(sum - target) < curMin) {
curMin = Math.abs(sum - target);
curSum = sum;
}
}
}
return curSum;
}
}
259. 3Sum Smaller
稍微变了变，利用 sum < target 时，i 和 left 不动，介于 left 和 right (包括 right) 之间的所有元素 sum 也一定小于 target 的单调性。
我记得有一道题和这个特别像，比这个要难，不是指针题，想不起来了。
public class Solution {
public int threeSumSmaller(int[] nums, int target) {
if (nums == null || nums.length < 3) return 0;
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) {
int sum = nums[i] + nums[left] + nums[right];
if (sum >= target) {
right--;
} else {
count += (right - left);
left++;
}
}
}
return count;
}
}
18. 4Sum
还是和3sum一个意思，注意去重。写到最后就跟套娃似的。
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; ++i) {
if (i != 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length - 2; ++j) {
if (j != i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left++]);
list.add(nums[right--]);
result.add(list);
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < target) {
left++;
} else right--;
}
}
}
return result;
}
}
454. 4Sum II
严格来说也不算指针题了，因为双指针的适用范围还是比较苛刻的，必须在单个的有序元素排列中，这道题给了四个数组，虽然我觉得题出的挺傻的，但是确实指针不好拿来用，如果把四个数组合并成一个，也不能排序，这是显然的。
所以这题就是用流行的方法，hashmap加nested for loop。
public class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < A.length; ++i) {
for (int j = 0; j < B.length; ++j) {
int sum = A[i] + B[j];
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
int result = 0;
for (int i = 0; i < C.length; ++i) {
for (int j = 0; j < D.length; ++j) {
result += map.getOrDefault(-1 * (C[i] + D[j]), 0);
}
}
return result;
}
}