转载：https://www.cnblogs.com/DarrenChan/p/8871495.html
1. 两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
LeetCode：https://leetcode-cn.com/problems/two-sum/description/
思路：
两层for循环时间复杂度是O(N)的想法大家应该都会，想想有没有时间复杂度更低的解法呢？
答案就是利用hashmap，这样可以用hashmap的key记录差值，value记录下标，在hashmap中进行查找的时间复杂度是O(1)，这样总的时间复杂度是O(N)。
public int[] twoSum(int[] a, int target) {
int[] res = new int[2];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < a.length; i++) {
if(map.containsKey(target-a[i])){
res[0] = map.get(target-a[i]);
res[1] = i;
break;
}
map.put(a[i],i);
}
return res;
}
2. 三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 *a + b + c = *0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
LeetCode：https://leetcode-cn.com/problems/3sum/description/
思路：
让时间复杂度尽可能小，先排序，时间复杂度可以是O(NlogN)，然后用三个指针遍历一次即可，这样总的时间复杂度是O(NlogN)。
当然也可以参考上道题，让hashmap进行记录，这样的话，需要记录两个值的组合，时间复杂度还是O(N^2)。
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> resultSet = new HashSet<List<Integer>>();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++) {
int j = i + 1;
int k = nums.length - 1;
while (j < k) {
if ((nums[i] + nums[j] + nums[k]) == 0) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
resultSet.add(list);
j++;
k--;
} else if ((nums[i] + nums[j] + nums[k]) < 0) {
j++;
} else {
k--;
}
}
}
return new ArrayList<List<Integer>>(resultSet);
}
//三个for循环，时间复杂度为 O(N^3)，超时
public List<List<Integer>> threeSum(int[] nums) {
Map<String,List<Integer>> resultMap = new HashMap<String, List<Integer>>();
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums.length;j++){
for(int k=0;k<nums.length;k++){
if(i!=j && j!=k && i!=k && nums[i]<=nums[j] && nums[j]<=nums[k] && (nums[i]+nums[j]+nums[k])==0){
List<Integer> triple = new ArrayList<Integer>();
String key = nums[i]+","+nums[j]+","+nums[k];
triple.add(nums[i]);
triple.add(nums[j]);
triple.add(nums[k]);
resultMap.put(key,triple);
}
}
}
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
result.addAll(resultMap.values());
return result;
}
