2Sum：
题目描述：
给定一个整型数组nums，一个target，从数组中找出a、b，使得a+b=target；并且假定数组中只有一对满足条件的a、b
原始思路：
用两个for循环遍历数组，找出结果，时间复杂度为O(n2)
优化思路：
使用hash表，建立HashMap<Integer, Integer> map，键值对为<nums[i]，i>。遍历数组nums，对每个数nums[i]，查询hash表中是否有key等于target-nums[i]的记录，若有，则找到；否则，将num[i]和下标i存入hash表。因为hash表的查找时间复杂度可以看作是O(1)，所以算法时间复杂度就降为O(n)了。
3Sum：
题目描述：
给定一个整型数组nums，从数组中找出所有不重复的[a,b,c]，使得a+b+c=0
原始思路：
3个for循环，但是超时了
优化思路：
使用双指针。首先将数组排序（防止重复），然后遍历数组，在每个位置i，设置双指针，左指针指向位置i+1，右指针指向位置nums.length-1，计算三个位置数之和，若等于0，则将三数位置下标加入结果集，左指针右移，右指针左移；若大于0，则右指针左移；若小于0，则左指针右移，直到左右指针相遇。遍历完数组，找到所有符合条件的[a,b,c]。为防止重复结果，若指针移动的下一个位置上的数与上一个位置上的数字相等，继续移动一位。这种方法的时间复杂度可以控制在O(n2)。
3SumClosest：
题目描述：
给定一个整型数组nums，一个target，从数组中找出3个数之和sum，使得sum与target差的绝对值最小
思路：
与3Sum类似，使用双指针。
4Sum：
题目描述：
给定一个整型数组nums，一个target，从数组中找出所有不重复的四元数组[a, b, c, d]，使得a+b+c+d = target
思路：
分解，将4Sum分解成3Sum再分解成2Sum，2Sum可以使用Hashmap或者双指针，从而将时间复杂度控制在O(n3)。实际代码实现中要注意避免重复的问题，并且可以使用一些判断条件（如：因为数组为升序，如果当前nums[i]*4 > target，就可以直接break了）进行速度优化。
具体实现：
public List<List<Integer>> fourSum(int[] nums, int target){ List<List<Integer>> res = new ArrayList<>(); // 数组为空或长度小于4，返回 if(nums == null || nums.length < 4) return res; //排序 Arrays.sort(nums); //数组太大或数组太小，返回 if(nums[0]*4 > target || nums[nums.length-1]*4 < target) return res; for(int i=0; i<nums.length-3; i++){ //注意判断条件不能是nums[i+1] == nums[i]，因为单组结果中可以出现重复的数字 if(i != 0 && nums[i-1] == nums[i]) continue; //避免重复 if(nums[i]*4 == target){ if(nums[i+3] == nums[i]){ res.add(Arrays.asList(nums[i], nums[i], nums[i], nums[i])); return res; } } if(nums[i] + 3*nums[nums.length-1] < target) continue; //nums[i]太小 if(nums[i] * 4 > target) return res; //nums[i]太大 threeSumForFourSum(nums, target-nums[i], i+1, res, nums[i]); } return res;}public void threeSumForFourSum(int[] nums, int target, int start, List<List<Integer>> res, int z1){ if(3*nums[start] > target || 3*nums[nums.length-1] < target) return; for(int i=start; i<nums.length-2; i++){ if(nums[i]*3 > target) return; //过大 if(nums[i] + nums[nums.length-1]*2 < target) continue; //过小 if(i != start && nums[i-1] == nums[i]) continue; //避免重复 if(3*nums[i] == target){ if(nums[i+2] == nums[i]){ res.add(Arrays.asList(z1,nums[i],nums[i],nums[i])); return; } } twoSumForFourSum(nums, target-nums[i], i+1, res, z1, nums[i]); }}public void twoSumForFourSum(int[] nums, int target, int start, List<List<Integer>> res, int z1, int z2){ if(start == nums.length-1) return; if(nums[start] *2 > target) return; HashMap<Integer, Integer> map = new HashMap<>(); for(int i= start; i<nums.length; i++){ if(i != start && nums[i-1] == nums[i]) continue; //避免重复 if(i!= nums.length-1 && 2*nums[i] == target){ if(nums[i+1] == nums[i]){ res.add(Arrays.asList(z1,z2,nums[i],nums[i])); } } int cut = target-nums[i]; if(map.containsKey(cut)){ res.add(Arrays.asList(z1,z2,cut,nums[i])); continue; } map.put(nums[i],i); }}
转载于:https://www.cnblogs.com/yingying7/p/11044215.html
相关资源：数据结构—成绩单生成器
