leetcode 1 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
暴力求解：直接两重for循环
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
但是之前提交的时候居然能超过100%，属实没想到，可能是那时候做这道题的人比较少吧。
后面碰巧又遇到这道题，这时候我又跑了一遍
暴力就只能超过25%，这就挺正常的。
接下来就是优化的地方
可以用哈希表，将数组的元素存进去，遍历的时候查找存不存在target - num[i],存在就说明找到了两个数的和为target，以空间换时间。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i< nums.length; i++) {
if(map.containsKey(target - nums[i])) {
return new int[] {map.get(target-nums[i]),i};
}
map.put(nums[i], i);
}
return new int[0];
}
}
还可以用排序 + 双指针的做法。
先给数组排序，双指针从两端开始向中间遍历。
但是题目要求返回的是数组的下标，给数组排序就会打乱数组的顺序，所以还得用集合记录原数组的元素所对应的下标。排序的时间复杂度为O(N *logN),遍历的时间复杂度为O(N)，整体时间复杂度为O(N *logN)，空间复杂度为O(N),而上面的单纯用哈希表的时间复杂度为O(N)，空间复杂度为O(N)，所以还是推荐用上面的哈希表的做法。这里就不贴代码了，可以自己实现，leetcode题解里面也可以找到。
但是，如果是返回和为target的两个元素的话，那么使用排序 + 双指针的做法就不需要开辟额外的空间了。
后面可以具体类推到3数之和和4数之和。
这里可以去看一下东哥的文章：
一个方法解决nSum的问题
或者去看看leetcode上面的题解。
下面是参考东哥的文章里的nSum的java版的实现。
存在不足的地方请多多指教。
/**
*
* @param nums 排序后的数组
* @param n n个数
* @param start 数组的起点
* @param target 目标和
* @return
*/
public List<List<Integer>> nSum(int[] nums, int n, int start, int target) {
int size = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (n < 2 || size < n) {
return res;
}
if (n == 2) {
int left = start;
int right = size - 1;
while (left < right) {
int sum = nums[left] + nums[right];
int leftVal = nums[left];
int rightVal = nums[right];
if (sum < target) {
while (left <right && nums[left] == leftVal) {
left++;
}
}
else if (sum > target) {
while (left < right && nums[right] == rightVal) {
right--;
}
}
else {
res.add(Arrays.asList(nums[left], nums[right]));
while (left < right && nums[left] == leftVal) {
left++;
}
while (left <right && nums[right] == rightVal) {
right--;
}
}
}
}
else {
for (int i = start; i < size; i++) {
List<List<Integer>> sub = nSum(nums, n - 1, i + 1, target - nums[i]);
for (List<Integer> arr : sub) {
List<Integer> arr_2 = new ArrayList<>(arr);
arr_2.add(nums[i]);
res.add(arr_2);
}
while (i < size - 1 && nums[i] == nums[i + 1]) {
i++;
}
}
}
return res;
}
看一下这里这段代码，为什么要重新new一个ArrayList呢
for (List<Integer> arr : sub) {
// (n-1)Sum 加上 nums[i] 就是 nSum
List<Integer> arr_2 = new ArrayList<>(arr);
arr_2.add(nums[i]);
res.add(arr_2);
}
如果只是按照下面的代码的实现，而不new一个ArrayList的话，就会报java.lang.UnsupportedOperationException这个错误。
for (List<Integer> arr : sub) {
arr.add(nums[i]);
res.add(arr);
}
这个错误其实是因为我们递归的时候也会用到 n == 2的时候的那部分代码中的Array.asList();而当我们所调用Arrays.asList()产生的List中add、remove方法时就会报异常，这是因为Arrays.asList()返回的是Arrays的内部类ArrayList，而不是java.util包下的ArrayList。Arrays的内部类ArrayList和java.util.ArrayList都是继承AbstractList，而remove、add等方法在AbstractList中是默认throw UnsupportedOperationException而且不作任何操作。java.util.ArrayList重写这些方法而Arrays的内部类ArrayList没有重写，所以会抛出异常。
因此new一个ArrayList就可以解决这个问题。
像leetcode的3数之和
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
return nSum(nums, 3, 0, 0);
}
像leetcode的4数之和
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return nSum(nums, 4, 0, target);
}
当然这只是通用解法。
对于3数之和，4数之和，都可以使用排序加双指针的的做法。