卷首语：
以前学习过一些数据结构和算法的课程，但都没怎么去付出实践，学完的第一感觉就是：我的脑子会了
实际自己动手写，虽然思路跟的上，还是会踩很多坑，代码漏洞频出。同一个问题，解决方式有很多种
最近打算在LeetCode上面刷题，自己写完的同时，学习学习大佬们的思路，拓宽见识
第一题：两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-permutation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
V1版本
这个题目看着就简单，废话不多话，先双重循环暴力破解试试
public int[] twoSum(int[] nums, int target) {
// 记录目标值与第一个加数的差值
int difference;
for (int i = 0; i < nums.length; i++) {
difference = target - nums[i];
for (int j = 0; j < nums.length; j++) {
// 同一个数只能用一次，遇到相同的跳过
if (i == j) {
continue;
}
if (nums[j] == difference) {
return new int[] {i, j};
}
}
}
// 没有找到
return null;
}
果然不出我所料
image.png
V2版本
v2版本是我想多了，开始相着数组里会没有负数，然后以先循环一遍，将大于target的数字过滤掉，
用一个新数组保存数字在原数组里的坐标，这样就只需要遍列一部份数字了，
在没有负数且target值在原数组中偏小时可能会有点优势
/**
* 原v1版本
*/
public int[] twoSumV1(int[] nums, int target) {
// 记录目标值与第一个加数的差值
int difference;
int i = 0, j;
for (; i < nums.length; i++) {
difference = target - nums[i];
j = 0;
for (; j < nums.length; j++) {
// 同一个数只能用一次，遇到相同的跳过
if (i == j) {
continue;
}
if (nums[j] == difference) {
return new int[] {i, j};
}
}
}
// 没有找到
return null;
}
public int[] twoSum(int[] nums, int target) {
// 保存记录数据值比 target 小的值坐标
int[] lowIndexArray = new int[nums.length];
int lowIndex = 0;
for (int i = 0; i < nums.length; i++) {
// 考虑有为0的数值,只有大于目标的值才过滤
if (nums[i] > target) {
continue;
}
lowIndexArray[lowIndex++] = i;
}
// 如果没有去掉任何数字，继续走V1
if (lowIndex == nums.length) {
return twoSumV1(nums, target);
}
// 没有答案
if (lowIndex == 0) {
return null;
}
// 截取lowIndexArray
int[] copy = new int[lowIndex];
System.arraycopy(lowIndexArray, 0, copy, 0,lowIndex);
return twoSum(lowIndexArray, nums, target);
}
public int[] twoSum(int[] indexs, int[] nums, int target) {
// 记录目标值与第一个加数的差值
int difference;
// 这里循环的是坐标
for (int i = 0; i < indexs.length; i++) {
// 这里需要先获取到下标值，在去原数据取得真实数据
difference = target - nums[indexs[i]];
for (int j = 0; j < indexs.length; j++) {
// 同一个数只能用一次，遇到相同的跳过
if (i == j) {
continue;
}
if (nums[indexs[j]] == difference) {
int[] result = {indexs[i], indexs[j]};
return result;
}
}
}
return null;
}
结果理所当然的错了，因为不支持负数
image.png
V3版本
v3版本开始想着要不要用散列表来处理，想着散列也需要空间和hash时间的消耗，效率应该也快不了多少，就没去实现了
结果去看官方的解题思路，也是用散列表来处理，想想也对，暴力破解的时间复杂度是O^2,数组比较大的时间，性能是成指数级下降的，参照着官方的两遍哈希表实现了一下，测试结果确实快了许多
后继看到官方的一遍哈希表文字提示，实现了一下，看到提示时觉得很简单，自信的提交了几次，全部失败了，后面才提交成功
/**
* 根据官方一遍hash表的思路，自己写的版本
*/
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return null;
}
// 用一个Map来保存数字与下标的对照关系
Map<Integer, Integer> numMap = new HashMap<>(getMapSizeBySize(nums.length));
// 先将第1条记录存入map
numMap.put(nums[0], 0);
int difference;
// 从下标一开始
int i = 1;
for (; i < nums.length; i++) {
difference = target - nums[i];
// 由于只会过一遍，不存在使用相同的数字，所以这里不需要要校验是否重复
if (numMap.containsKey(difference)) {
return new int[] {i, numMap.get(difference)};
}
// 一定要放下面
numMap.put(nums[i], i);
}
return null;
}
/**
* 获取map初始化的值的大小
*/
public static int getMapSizeBySize(int size) {
return size * 4 / 3 + 2;
}
image.png
后面会继续刷题，如果有大佬有更好的思路希望能向大佬学习，感谢指点
网友评论