数组中 n 个数的和为 0 问题
1. Two Sum
给定一组数，找出其中和为 0 的两个数，很简单的想法，使用 HashMap，键为数组元素，值为数组索引。遍历数组，赋值，同时检测数据元素的相反数是否包含在 map 中，如果包含，得到其索引，然后返回
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
int rArray[] = new int[2];
for(int i = 0;i<nums.length;i++){
Integer anotherIndex = map.get(target - nums[i]);
if(anotherIndex !=null && anotherIndex != i){
rArray[0] = anotherIndex;
rArray[1] = i;
return rArray;
}
map.put(nums[i],i);
}
return null;
}
}
15. 3Sum
给定一组数，找出其中和为 0 的三个数。
public class Solution {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
public List<List<Integer>> threeSum(int[] num) {
if(num == null || num.length < 3) return ret;
Arrays.sort(num);
int len = num.length;
for(int i = 0; i < len-2; i++){
if(num[i] > 0){
break;
}
if(i > 0 && num[i] == num[i-1]) continue;
find(num, i+1, len-1, num[i]);
}
return ret;
}
public void find(int[] num, int begin, int end, int target){
int l = begin;
int r = end;
while(l < r){
if(num[l] + num[r] + target == 0){
List<Integer> ans = new ArrayList<Integer>();
ans.add(target);
ans.add(num[l]);
ans.add(num[r]);
ret.add(ans);
while(l < r && num[l] == num[l + 1]) l++; //为了防止重复,遇见相同的就直接跳过
while(l < r && num[r] == num[r - 1]) r--;
l++;
r--;
} else if(num[l] + num[r] + target < 0){
l++;
} else{
r--;
}
}
}
}
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ll = new ArrayList<List<Integer>>();
Arrays.sort(nums);
for(int i = 0;i< nums.length; i++ )
{
if(i > 0 && nums[i] == nums[i-1])
continue;
List<Set<Integer>> rls = twoSum(nums, -nums[i], i, i); // 缩减时间复杂度的关键？
for(Set<Integer> rl: rls){
List<Integer> nl = new ArrayList(rl);
if(rl.size()<3){ // 因为 set 类型中不能有重复数据，因此例如 2,2-4 这种组合最终会变成 2,-4
int temp = 0;
for(Integer elem:nl){
temp = temp - elem;
}
nl.add(temp);
if(temp == 0) // 因为 set 类型中不能有重复元素，因此例如 0,0,0 这种组合会变成 0
nl.add(0);
}
ll.add(nl);
}
}
return ll;
}
public List<Set<Integer>> twoSum(int[] nums, int target, int j, int start){
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
List<Set<Integer>> rls = new ArrayList<Set<Integer>>();
for(int i = start;i<nums.length;i++){
if(i == j) // 一旦遇到 target 元素所在位置，跳过本次循环
continue;
Integer anotherIndex = map.get(target - nums[i]);
if(anotherIndex !=null && anotherIndex != i ){
Set<Integer> temps = new HashSet<Integer>();
temps.add(nums[anotherIndex]);
temps.add(nums[i]);
temps.add(-target);
if(!rls.contains(temps)){
rls.add(temps);
}
}
map.put(nums[i],i); // 将 nums[i] 和 i 映射添加到 map 中，防止重合
}
return rls;
}
}
