算法细节系列（29）：any sum
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434793
算法细节系列（29）：any sum
详细代码可以fork下Github上leetcode项目，不定期更新。
题目摘自leetcode：
Leetcode 001. Two Sum
头号种子啊，刷leetcode第一题就是它，带我入门带我飞。说说当初的思路吧，好幼稚。
顺序遍历所有pair对，把符合的target的sum挑出来。代码如下：
public int[] twoSum(int[] nums, int target) {
int[] array = new int[2];
for(int i =0;i<nums.length;i++){
array[0]=i;
for (int j =i+1;j<nums.length;j++){
array[1]=j;
if(nums[i]+nums[j]==target){
return array;
}
}
}
return array;
}TWO SUM的题目可以在O(n)O(n)的时间复杂度内解决战斗。思路：
find:
nums[i] + nums[j] = target
也就是说find:
nums[i] = target - nums[j]
查找一个元素最快的方法可以用map来解决。代码如下：
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[1] = i;
result[0] = map.get(target - nums[i]);
return result;
}
map.put(nums[i], i);
}
return result;
}貌似这种假想一个可能存在可能不存在的元素很常见（target - numsj）。
Leetcode 015. 3Sum
刚开始的想法也是用一个MAP去存放所有的nums[i] + nums[j]的组合，接着遍历一遍数组，去找和为key = 0 - nums[k]的组合，时间复杂度能控制在O(n2)O(n^2)，但很可惜这种方法没有解决duplicate问题。
思路：
- 对数组进行排序，很关键，为了在搜索时，能把O(n2)O(n^2)复杂度降低到O(n)O(n)
- 把3sum问题归简为查找2sum问题。
先看代码：
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++){
int target = -nums[i];
int lf = i + 1;
int rt = nums.length - 1;
while (lf < rt){
int sum = nums[lf] + nums[rt];
if (sum < target) lf++;
if (sum > target) rt--;
if (sum == target){
Integer[] triple = new Integer[3];
triple[0] = nums[i];
triple[1] = nums[lf];
triple[2] = nums[rt];
ans.add(Arrays.asList(triple));
while (lf < rt && nums[lf] == triple[1]) lf++;
while (lf < rt && nums[rt] == triple[2]) rt--;
}
}
while (i + 1 < nums.length && nums[i+1] == nums[i]) i++;
}
return ans;
}起初困扰我的两点：
- 为何for循环遍历过的元素，在找TWO SUM的解时，不在考虑了？（lf = i + 1，只考虑i后面的元素）
- 这种while循环结构怎么就能确保找到了所有TWO SUM的解。
第一个问题，可以想象，假设遍历过的k元素，是在遍历i元素时（i > k），TWO SUM的一个解，由于代码查找的结构，一定在遍历k时，找到了TWO SUM中的某个i元素，而不会等到遍历i元素才找到k元素，解决了我之前重复的大问题。
第二个问题，它的查找复杂度为O(n)O(n)，原因在于数组有序，所以当:
sum = nums[lf] + nums[rt];
如果 sum < target
表明：nums[lf] + nums[rt'] < nums[lf] + nums[rt] < target
其中 rt' 在 (lf + 1, rt -1)范围内，这些组合都不必再考虑
同理：
如果 sum > target
target < nums[lf'] + nums[rt],lf后续的下标也不必考虑
所以每次我们只要比较边界即可
if sum < target lf++;
if sum > target rt--;Leetcode 018. 4Sum
思路和3SUM一样，没什么特别的地方。代码如下：
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; ++i){
for (int j = i + 1; j < nums.length; ++j){
int key = target - nums[i] - nums[j];
int lf = j + 1;
int rt = nums.length - 1;
while (lf < rt){
int sum = nums[lf] + nums[rt];
if (sum < key) lf++;
if (sum > key) rt--;
if (sum == key){
ans.add(Arrays.asList(nums[i],nums[j],nums[lf],nums[rt]));
while (lf < rt && nums[lf + 1] == nums[lf]) lf++;
while (lf < rt && nums[rt - 1] == nums[rt]) rt--;
lf++;
rt--;
}
}
while (j + 1 < nums.length && nums[j+1] == nums[j]) j++;
}
while (i + 1 < nums.length && nums[i+1] == nums[i]) i++;
}
return ans;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017年06月06日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
