LeetCode：1. 两数之和

思路

1. 暴力破解法：两个循环遍历找出相加等于目标值的元素后返回数组，复杂度O(n²)
2. 哈希映射法，需要一点点逆向的思考，题目给出的是相加等于目标值，那么我们通过用目标值减去我们当前遍历的对象，就能知道我们要找到的值是多少了，用Hash是能快速获取到我们已经遍历过的元素，复杂度O(1)
   • 将传入数组的每个元素都作为Map集合的键，下标作为值；
   • 遍历元素时将target-当前遍历元素作为键去获取Map集合的值；
   • 当值不存在，说明当前遍历的元素在我们已遍历过的元素中不存在相加等于target的值，即还没找到第二个下标，并将当前元素放入Map集合中，便于后续遍历到其他元素时查找我们已遍历过的元素；
   • 当值存在时，说明我们找到了第二个下标，赋值到两个元素的数组中返回

注意事项及错误反思

1. 每个元素不能使用两次，如果用下面的Hash法1，需要注意这个问题
2. 数组中有且仅有仅有一个答案
3. 代码结尾要记得写return null;，在没有编译器的帮助下容易遗漏代码

代码

// 暴力破解法
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
        return null;
    }
}
// Hash法1
class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 先声明map集合存放每个元素对应的下标
        Map<Integer,Integer> map = new HashMap<>();
        for (int i=0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        int[] rt = new int[2];
        for (int i=0; i< nums.length; i++){
rt[0]=i;
Integer beiJianShuIndex = map.get(target-nums[i]);
// 由于预先把值放到了map集合中，所以会使用到与当前遍历值同一对象
// 需要多做一层判断
            if (beiJianShuIndex != null && beiJianShuIndex != i){
                rt[1] = map.get(target-nums[i]);
                return rt;
            }
        }
        return rt;
    }
}

// Hash法2，优化后的写法（官方写法）
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        int[] rt = new int[2];
        // 移除了一开始将所有值放入Map集合中，在一次循环中即可取得正确答案，
        // 还无须判断当前值是否重复使用
        for (int i=0; i< nums.length; i++){
rt[0]=i;
Integer beiJianShuIndex = map.get(target-nums[i]);
            if (beiJianShuIndex != null) {
                rt[1]=map.get(target-nums[i]);
                return rt;
            }
            map.put(nums[i], i);
        }
        return rt;
    }
}

题目链接

1. 两数之和

原文地址：https://blog.csdn.net/qq_28194001/article/details/143897256

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！