解
第一步，万年不变的查错。如果给的array是null或不够两个数，直接return 0
public int twoSum6(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return 0;
}
...
}
后面的思路，我的方式和九章上的答案不大一样。九章用的Two Pointer，我用了两个HashSet。大体思路就是，这个题和最简单的TwoSum唯一的区别就是，需要找到所有长度为2的组合，且不能重复。既然要找到所有的且去重，那就用HashSet搞定了。
我们需要创建一个class Pair，用来放这两个数字。在constructor里面，我对比了一下数字的大小，然后小的是a，大的是b，这样就可以保证HashCode不会因为两个数字反过来就不一样了。
private class Pair {
int a;
int b;
public Pair(int a, int b) {
if (a <= b) {
this.a = a;
this.b = b;
} else {
this.a = b;
this.b = a;
}
}
@Override
public boolean equals(Object o) {
if (o instanceof Pair) {
Pair other = (Pair) o;
return this.a == other.a && this.b == other.b;
}
return false;
}
@Override
public int hashCode() {
int result = a;
result = 31 * result + b;
return result;
}
}
然后建一个HashSet用来存放所有找到的Pair和去重
Set<Pair> pairs = new HashSet<>();
然后这道题继续以TwoSum的解法，建一个HashSet来存放见过的数字，然后遍历整个array，如果之前见过target - currentNumber的数字，就建一个Pair，放到pairs里面。在放的过程中，HashSet会自动的根据hashCode和equals去重，即如果hashCode是一样的，就会呼叫equals，如果返回true，那就不做任何更改（并且return false，不过我们不需要关心它的return）。到最后，只需要return pairs.size()就可以知道有多少个了。如果这道题要变成需要知道具体是哪几个组合，这个做法也直接解决了。
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(target - nums[i])) {
pairs.add(new Pair(target - nums[i], nums[i]));
}
set.add(nums[i]);
}
return pairs.size();
这里要先建pair，再把当前的数字加到set里面，因为题目要求不能重复用两个数字。如果可以用，那么就把set.add(nums[i])放到for loop的一开始就好了。
完整的code
public class Solution {
/*
* @param nums: an array of integer
* @param target: An integer
* @return: An integer
*/
private class Pair {
int a;
int b;
public Pair(int a, int b) {
if (a <= b) {
this.a = a;
this.b = b;
} else {
this.a = b;
this.b = a;
}
}
@Override
public boolean equals(Object o) {
if (o instanceof Pair) {
Pair other = (Pair) o;
return this.a == other.a && this.b == other.b;
}
return false;
}
@Override
public int hashCode() {
int result = a;
result = 31 * result + b;
return result;
}
}
public int twoSum6(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return 0;
}
Set<Pair> pairs = new HashSet<>();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(target - nums[i])) {
pairs.add(new Pair(target - nums[i], nums[i]));
}
set.add(nums[i]);
}
return pairs.size();
}
}
九章
九章上答案的思路是，先对array进行排序。
Arrays.sort(nums);
然后设count为0，两根指针，一左一右，向中间行进。
int count = 0;
int left = 0, right = nums.length - 1;
while (left < right) {
...
}
如果两个数字是一样的，那么count++，然后左边指针往右移，右边指针往左移，并且如果当前数字和上一个数字相同，那么跳过接着移动，当然全程要保持左边的指针不能超过右边的指针。
int sum = nums[left] + nums[right];
if (sum == target) {
count++;
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
}
如果当前的和大于target，那么就右边往左移，如果当前的和小于target，那么就左边往右移。
else if (sum > target) {
right--;
} else {
left++;
}
最后返回count就可以了。
完整的code
public class Solution {
/**
* @param nums an array of integer
* @param target an integer
* @return an integer
*/
public int twoSum6(int[] nums, int target) {
// Write your code here
if (nums == null || nums.length < 2)
return 0;
Arrays.sort(nums);
int count = 0;
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
count ++;
left ++;
right --;
while (left < right && nums[right] == nums[right + 1]) {
right --;
}
while (left < right && nums[left] == nums[left - 1]) {
left ++;
}
} else if (sum > target) {
right --;
} else {
left ++;
}
}
return count;
}
}
分析
时间复杂度（time complexity)
我的解法应该是O(n)，n为array的长度。因为只遍历的array一次。HashSet的插入和读取皆为O(1)。相较于九章的解法，一开始先sort array，时间复杂度为O(nlogn)，这个解法的时间复杂度要低一点。
空间复杂度 （space complexity)
我的解法是O(n)，建立了两个HashSet，每个为O(n)。相较于九章的算法，O(1)，这个解法的空间复杂度要高一点。
整体来说，九章的解法更短，不过这是因为我的解法需要写一个class。真正的逻辑而言，我的逻辑更为简练。九章的解法是in place，没有用到任何额外的memory，而我的用到了O(n)的额外空间。当与面试官说清楚，两种解法各有利弊，应都熟练掌握。
网友评论